最长定差子序列（Longest Arithmetic Subsequence of Given Difference）

题目描述

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

注意：子序列 意味着可以不连续，但顺序必须与原数组保持一致。

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

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

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

解题过程（循序渐进）

步骤 1：理解问题

我们不需要关心任意公差，只需要公差恰好为 difference 的等差子序列。
因为是子序列，我们可以跳过中间的元素，但必须保持顺序。
目标：找出最长的这种子序列的长度。

步骤 2：观察子问题结构

假设我们想知道以 arr[i] 结尾的、公差为 difference 的最长等差子序列的长度。
如果我们知道在这个子序列中，arr[i] 的前一个元素应该是 prev = arr[i] - difference，
那么只需要找到在 i 之前，以 prev 结尾的最长子序列长度，然后加 1 即可。

关键：因为数组是无序的，我们不能直接通过下标找上一个元素的位置。但我们可以用哈希表记录以某个值结尾的最长子序列长度。

步骤 3：定义状态

定义：
dp[x] 表示以值 x 结尾的、公差为 difference 的最长等差子序列的长度。

注意：这里的 x 是数组中的某个值，不是下标。
因为我们需要快速找到 x - difference 对应的长度，所以用哈希表（字典）存储。

步骤 4：状态转移方程

当我们遍历到 arr[i] 时，设当前值为 val，则它的前一个数应该是 prev = val - difference。
检查 prev 是否在之前被记录过（即是否已出现在 dp 中）：

• 如果 prev 存在，说明可以接在某个以 prev 结尾的子序列后面，新长度 = dp[prev] + 1。
• 如果 prev 不存在，那么以 val 结尾的子序列暂时只有它自己，长度为 1。

所以：
dp[val] = dp.get(prev, 0) + 1

同时，我们需要在遍历过程中更新全局最大值。

步骤 5：举例推导

示例：arr = [1,5,7,8,5,3,4,2,1], difference = -2

初始化：dp = {}, ans = 0

1. i=0, val=1, prev=3 → 没有 3，dp[1] = 1, ans=1
2. i=1, val=5, prev=7 → 没有 7，dp[5] = 1, ans=1
3. i=2, val=7, prev=9 → 没有 9，dp[7] = 1, ans=1
4. i=3, val=8, prev=10 → 没有 10，dp[8] = 1, ans=1
5. i=4, val=5, prev=7 → dp[7]=1，所以 dp[5] = dp[7] + 1 = 2，更新 ans=2
6. i=5, val=3, prev=5 → dp[5]=2，所以 dp[3] = 2 + 1 = 3，ans=3
7. i=6, val=4, prev=6 → 没有 6，dp[4] = 1
8. i=7, val=2, prev=4 → dp[4]=1，所以 dp[2] = 1 + 1 = 2
9. i=8, val=1, prev=3 → dp[3]=3，所以 dp[1] = 3 + 1 = 4，ans=4

最终 ans=4，对应子序列 [7,5,3,1]。

步骤 6：算法步骤

1. 初始化一个空字典 dp，用于存储“以某个值为结尾的最长子序列长度”。
2. 初始化 ans = 0。
3. 遍历数组 arr 的每个值 x：
   • 计算前一个值 prev = x - difference
   • 从 dp 中获取 prev 对应的长度，如果不存在则为 0
   • 当前以 x 结尾的长度为 length = dp.get(prev, 0) + 1
   • 更新 dp[x] = length
   • 更新 ans = max(ans, length)
4. 返回 ans

步骤 7：复杂度分析

• 时间复杂度：O(n)，因为只需要遍历一次数组，字典的插入和查询平均 O(1)
• 空间复杂度：O(n)，用于存储字典

步骤 8：边界与注意事项

• 数组元素可能为负数，也可能 difference 为负数，但哈希表处理负数的 key 没有问题
• 数组可能很长，但算法是线性的，很高效
• 如果有重复的元素（如示例中 5 和 1 出现两次），哈希表会覆盖为最新的长度，这是正确的，因为后面的可以接在前面相同的值形成的子序列后面，但长度可能变大，所以更新是必要的

步骤 9：代码示例（Python）

def longestSubsequence(arr, difference):
    dp = {}
    ans = 0
    for x in arr:
        prev = x - difference
        length = dp.get(prev, 0) + 1
        dp[x] = length
        if length > ans:
            ans = length
    return ans

小结

这个题目是线性动态规划的经典应用，通过哈希表存储以某个值结尾的最优解，从而在 O(1) 时间内找到前驱状态。
核心是抓住“公差固定”这一条件，将子序列的连续性转化为对“前一个元素值”的查找。