题目地址：

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

给定一个长$n$数组$A$，和一个数$d$，问$A$中以$d$为公差的等差子序列的最长长度。

设$f[x]$为以$x$结尾的最长等差子序列的最长长度（可以将$f$视为一个哈希表）。在遍历$A$的时候时刻维护$A[0:i]$这个区间的$f$对应的信息。当遍历到$A[i]$的时候，$A[0:i-1]$的$f$的信息已经求出，则以$A[i]$为结尾的最长子序列的长度应该是$f[A[i]-d]+1$（如果$A[i]-d$不存在，则$f[A[i]-d]$取$0$）。代码如下：

class Solution {public:int longestSubsequence(vector<int>& v, int d) {unordered_map<int, int> mp;int res = 0;for (int x : v) {if (!mp.count(x - d)) mp[x] = 1;else mp[x] = 1 + mp[x - d];res = max(res, mp[x]);}return res;}
};

时空复杂度$O(n)$。