LeetCode 1218. 最长定差子序列（哈希map）

示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。
 
提示：
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4

class Solution {	//C++
public:
    int longestSubsequence(vector<int>& arr, int difference) {
    	unordered_map<int,int> m;//等差数列结尾的数，最大长度
    	int maxlen = 1;
    	for(int i = 0, prev; i < arr.size(); ++i)
    	{
    		prev = arr[i]-difference;
    		if(m.count(prev))//前面有一个数与我构成等差数列
    			m[arr[i]] = m[prev] + 1;
    		else
    			m[arr[i]] = 1;
    		maxlen = max(maxlen, m[arr[i]]);
    	}
    	return maxlen;
    }
};

class Solution:# py3
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d = {}
        maxlen = 1
        for i in range(len(arr)):
            if arr[i]-difference in d:
                d[arr[i]] = d[arr[i]-difference] + 1
            else:
                d[arr[i]] = 1
            maxlen = max(maxlen, d[arr[i]])
        return maxlen