最长定差子序列 图解题解

这道题到底在问什么

arr

[1,5,7,8,5,3,4,2,1]

difference

-2

输出

4

解释

选 7,5,3,1(每步 -2)，长度 4

先想最直接的笨办法

公差固定让前驱唯一，所以每个数只做一次哈希查 + 一次写，整体 O(n)。这正是比 1027(公差要枚举，O(n²))简单的地方。（动画第 29 步）

最优解：一步一步想明白

1. 3可以，但那样对每个起点都要往后扫一遍，最坏 O(n²)。我们想要一遍扫完。换个角度想：与其往后找，不如往回看「我的前一项在没在」。
2. 4对每个数当起点，反复在后面找「当前值 + difference」，凑出一条链。多个起点的链会大量重算，整体 O(n²) 甚至更糟。我们要把「往后找」翻转成「往回查一次」。
3. 5注意这里 dp 的下标是数值本身，不是数组位置。因为公差固定，一个数 v 能接到谁后面是唯一确定的——只能接在值为 v − difference 的那个数后面。
4. 6扫到 v 时，去查它的前驱 v−difference 当前的 dp 值：查得到就 +1 接上去，查不到就说明 v 是新链的开头(长度 1)。前驱要是已经在 v 左边出现过就在表里、查得到；还没出现就查不到、让 v 自己开新链——所以从左往右扫天然满足顺序。下面用 difference = −2，前驱就是 v+2。
5. 7arr 长度 9 · difference = −2这排是原数组，格子下方小数字是下标。公差固定为 −2，意味着 v 只能接在值 v+2 的数后面。下面下方会出现一张哈希表 dp{值→长度}，随扫描一格格长出来。
6. 8答案链 7→5→3→1提前剧透答案：绿色的 7、5、3、1(下标 2、4、5、8)隔着别的数取出来，两两差 −2。接下来看 dp 怎么从左到右把这条链一节一节接出来。
7. 9查 dp[1+2]=dp[3]第一个数 值1(下标0)。先算前驱 1+2=3，去 dp 表里查——表还空着，查不到 3。
8. 101 是开头，dp[1]=1没查到前驱 → 1 自己是开头，dp[1]=1。dp 表里新增一行「1 → 1」(绿色高亮的就是刚写入的)。
9. 11查 dp[5+2]=dp[7]值5(下标1)。前驱 7，但 7 在更右边还没扫到，dp 表里查不到。
10. 125 暂为开头，dp[5]=1查不到 7 → 5 暂时也是开头，dp[5]=1。表里多一行「5 → 1」。
11. 13查 dp[7+2]=dp[9]值7(下标2)。前驱 9 不存在。别小看现在的 7，它正是答案链的头。
12. 147 开头，dp[7]=1写入 dp[7]=1，新增「7 → 1」。记牢这行——后面 5、3、1 会一节节接到它后面。
13. 15查 dp[8+2]=dp[10]值8(下标3)。前驱 10 不存在，8 是个对答案没用的旁支。
14. 168 开头，dp[8]=1dp[8]=1，照记「8 → 1」。算法一视同仁，不管是不是答案链。
15. 17查 dp[5+2]=dp[7]=1又见 值5(下标4)。前驱 7 这次命中了(蓝色高亮那行 dp[7]=1)! 数组里下标2 的 7 也点亮了——5 能接到它后面。
16. 18dp[5] 由 1 升到 2dp[5] = 1+1 = 2。原来的「5 → 1」被覆盖成「5 → 2」(同一个值只留最长)。链 7→5 拼成长度 2。
17. 19查 dp[3+2]=dp[5]=2值3(下标5)。前驱 5 命中，且 dp[5] 已经是 2(那条 7→5 链)! 3 能接到这条更长的链后面。
18. 20dp[3]=3dp[3] = 2+1 = 3，新增「3 → 3」。链变成 7→5→3，长度 3。一节一节接出来了。
19. 21查 dp[4+2]=dp[6]值4(下标6)。前驱 6 从没出现过，又是一条新开头。
20. 22dp[4]=1dp[4]=1，新增「4 → 1」。4 也是旁支，对最长链没贡献。
21. 23查 dp[2+2]=dp[4]=1值2(下标7)。前驱 4 命中，dp[4]=1。2 能接到 4 后面，但这只是条短旁支。
22. 24dp[2]=2dp[2] = 1+1 = 2，新增「2 → 2」。这条 4→2 旁支长度才 2，比不过主链的 3。
23. 25查 dp[1+2]=dp[3]=3最后的 值1(下标8)! 前驱 3 命中，而 dp[3]=3(就是那条 7→5→3)! 数组里下标5 的 3 也点亮——1 要接到主链尾巴。
24. 26dp[1] 由 1 升到 4dp[1] = 3+1 = 4! 开头那行「1 → 1」被覆盖成「1 → 4」。主链 7→5→3→1 终于拼成长度 4!
25. 27答案 = max(dp 所有值) = 4全扫完了，看 dp 表里的最大值：4(来自 dp[1])。它对应的链就是高亮的 7→5→3→1，下标 2、4、5、8。和示例答案 4 完全对上。
26. 287 → 5 → 3 → 1，每步 −2回放这条绿链：下标 2、4、5、8 的 7、5、3、1，跳过中间的数，公差恒为 −2。dp 正是靠「每个数只查唯一前驱 v−difference」一节一节接出来的——一遍扫完，干净利落。
27. 29公差固定让前驱唯一，所以每个数只做一次哈希查 + 一次写，整体 O(n)。这正是比 1027(公差要枚举，O(n²))简单的地方。
28. 32因为公差固定时，「v 该接谁」只由数值决定(接值为 v−difference 的那个)，和它在哪个下标无关。用数值当键，查前驱一步到位。1027 公差不定，才要 dp[下标][公差] 两维。
29. 34i=4 值5 误查 5−2=3如果把前驱错算成 v−difference 又把 difference 当 +2，扫到 5 时会去查 dp[3](不存在)，结果 5 接不到前面的 7，主链断在第一节，答案错成 1。正确是查 5−(−2)=7，命中 dp[7]=1 才接得上。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def longestSubsequence(self, arr, difference):
        dp = {}            # dp[v]=以值v结尾的最长长度
        ans = 0
        for v in arr:
            dp[v] = dp.get(v - difference, 0) + 1   # 接前驱
            if dp[v] > ans:
                ans = dp[v]
        return ans

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int,int> dp;   // dp[v]
        int ans = 0;
        for (int v : arr) {
            dp[v] = dp[v - difference] + 1;   // 接前驱
            ans = max(ans, dp[v]);
        }
        return ans;
    }
};

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer,Integer> dp = new HashMap<>();  // dp[v]
        int ans = 0;
        for (int v : arr) {
            int prev = dp.getOrDefault(v - difference, 0);
            dp.put(v, prev + 1);            // 接前驱
            ans = Math.max(ans, dp.get(v));
        }
        return ans;
    }
}

复杂度

面试官可能追问