最长等差子序列的长度（给定差值diff）

题目描述

给定一个整数数组 nums 和一个整数 diff，你需要找出并返回最长等差子序列的长度，这个等差数列的公差是给定的 diff。
注意：子序列不一定连续，但必须保持原数组中的相对顺序。
示例：

输入：nums = [1, 5, 7, 8, 5, 3, 4, 2, 1], diff = -2
输出：4
解释：最长的等差子序列是 [7, 5, 3, 1]，其公差为 -2，长度为 4。

解题思路

这个问题是最长定差子序列（Longest Arithmetic Subsequence of Given Difference）的一个具体化版本，但更简单，因为公差是固定给定的，所以可以用线性动态规划配合哈希表高效解决。

步骤 1：定义状态

设 dp[x] 表示以数值 x 结尾的、公差为 diff 的等差子序列的最大长度。
注意：x 是数组中的某个元素值，而不是下标。

步骤 2：状态转移

对于数组中的当前数字 nums[i]，要想形成公差为 diff 的等差数列，它前面一个数应该是 prev = nums[i] - diff。

• 如果 prev 在之前的遍历中出现过，并且我们知道以 prev 结尾的最长等差子序列长度，那么 nums[i] 可以接在它后面，长度加 1。
• 即：

\[dp[\text{nums}[i]] = dp[\text{nums}[i] - \text{diff}] + 1 \]

• 如果 prev 没出现过，则 nums[i] 自己作为一个序列开头，长度为 1。

因为子序列不要求连续，只要 prev 在数组中出现在当前元素之前即可，所以我们在遍历时一边更新 dp，就可以自然保证顺序。

步骤 3：初始条件

每个单独的数都可以作为一个长度为 1 的等差序列，所以：

\[dp[x] = 1 \quad (\text{初始值，当第一次遇到 x 时}) \]

在代码中，我们可以用哈希表（字典）来实现 dp，初始时为空，遇到新数字时默认长度为 1。

步骤 4：遍历与更新

我们顺序遍历 nums，对每个 nums[i]：

1. 计算 prev = nums[i] - diff
2. 在哈希表中查找 prev 对应的长度，如果存在，则 dp[nums[i]] = dp[prev] + 1，否则 dp[nums[i]] = 1（但我们可以统一写成 dp.get(prev, 0) + 1）。
3. 更新哈希表中 nums[i] 对应的长度为上一步计算的值。
4. 同时记录遍历过程中的最大长度。

步骤 5：举例推导

以示例 nums = [1, 5, 7, 8, 5, 3, 4, 2, 1], diff = -2 为例：

初始化哈希表 dp = {}，ans = 0。

1. i=0, nums[0]=1, prev=1-(-2)=3, dp.get(3,0)=0 → dp[1]=1, ans=1
dp = {1:1}
2. i=1, nums[1]=5, prev=5-(-2)=7, dp.get(7,0)=0 → dp[5]=1, ans=1
dp = {1:1, 5:1}
3. i=2, nums[2]=7, prev=7-(-2)=9, 无 → dp[7]=1
dp = {1:1, 5:1, 7:1}
4. i=3, nums[3]=8, prev=10, 无 → dp[8]=1
5. i=4, nums[4]=5, prev=7, dp[7]=1 → dp[5] = 1+1=2 (更新)
   dp = {..., 5:2} (表示以 5 结尾的等差序列长度是 2，即 [7,5])，ans=2
6. i=5, nums[5]=3, prev=5, dp[5]=2 → dp[3] = 2+1=3 (序列 [7,5,3])，ans=3
7. i=6, nums[6]=4, prev=6, 无 → dp[4]=1
8. i=7, nums[7]=2, prev=4, dp[4]=1 → dp[2] = 1+1=2
9. i=8, nums[8]=1, prev=3, dp[3]=3 → dp[1] = 3+1=4 (序列 [7,5,3,1])，ans=4

最终答案为 4。

步骤 6：时间复杂度与空间复杂度

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(n)，哈希表最多存储 n 个键值对。

代码示例（Python）

def longestSubsequence(nums, diff):
    dp = {}
    ans = 0
    for num in nums:
        prev = num - diff
        # 如果 prev 在 dp 中，则接在后面，否则长度为 1
        dp[num] = dp.get(prev, 0) + 1
        ans = max(ans, dp[num])
    return ans

关键点总结

1. 因为公差固定，只需要知道以某个值结尾的最长长度，不需要二维数组，一维哈希表即可。
2. 状态转移依赖于“前一个数”是否存在，所以哈希表查询是 O(1)。
3. 遍历时自然保证了顺序，因为每次查询的 prev 是之前遍历中可能遇到的值，如果没遇到，说明它要么在后面（将来可能遇到但不影响当前计算），要么不存在。

这样我们就用线性动态规划高效解决了固定公差的最长等差子序列问题。