题目描述：

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

方法一：

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int, int> maps;int ans = 1;for (int i = 0; i < arr.size(); i++){maps[arr[i]] = maps[arr[i] - difference] + 1;ans = max(ans, maps[arr[i]]);}return ans;}
};

可能是平时没怎么接触过、用过dp，这么简单的问题居然想了好久。。

方法二：

class Solution {
int maps[40001];
public:int longestSubsequence(vector<int>& arr, int difference) {int ans = 1;for (int i = 0; i < arr.size(); i++){maps[arr[i] + 20000] = maps[arr[i] + 20000 - difference] + 1;ans = max(ans, maps[arr[i] + 20000]);}return ans;}
};

数据量较小的情况下，用数组肯定是比哈希表快的，但是由于有负数想不到怎么将负数转化成数组的下标，看了下别人的题解，原来可以这样：由于 -10000 <= arr[i], difference <= 10000 ，所以可以开一个大小为40001的数组，遍历到的每个数字都加上20000，这样就可以存进去负数了。