最长等差数列 图解题解

这道题到底在问什么

nums

[9,4,7,2,10]

输出

3

解释

选 4、7、10(公差 +3)，长度 3，是最长的

先想最直接的笨办法

如果公差给定，这题就退化成「固定差值的最长等差子序列」——仍是子序列、可以跳着挑，只少枚举公差这一维，用值到长度的哈希表扫一遍即可。麻烦在于公差没给、可正可负、范围很大，得想个办法让每种公差各自记一笔账。（动画第 3 步）

最优解：一步一步想明白

1. 3如果公差给定，这题就退化成「固定差值的最长等差子序列」——仍是子序列、可以跳着挑，只少枚举公差这一维，用值到长度的哈希表扫一遍即可。麻烦在于公差没给、可正可负、范围很大，得想个办法让每种公差各自记一笔账。
2. 4暴力枚举公差再逐个匹配，慢且乱。换个视角：固定以某个数结尾，再问「它前面哪个数能接上来」，这就有了 DP 的味道。
3. 5对每个 i，枚举它前面的 j：公差 d = nums[i] − nums[j]。那么把 nums[i] 接到「以 nums[j] 结尾、同样公差 d」的串后面，长度 +1。公差用哈希表当下标，多少种差都装得下。
4. 6若 j 那里本来没有公差 d 的记录，说明 nums[j] 是这串的开头，按长度 1 起算，接上 nums[i] 就是 2。下面用示例 [9,4,7,2,10] 一对一对地填这张表。
5. 7下标 0..4下面这排是原数组，格子下方的小数字是下标 i。算法外层循环让 i 从 1 走到 4，内层让 j 扫遍 i 左边所有位置，逐对算公差。
6. 8答案藏在 4、7、10提前把答案点出来：绿色的三个数 4、7、10(下标 1、2、4)隔着 9 和 2 取出来，两两差 +3。接下来看 DP 怎么把这条链一格一格拼出来。
7. 9i 从下标 1 起步正式开扫。外层 指针 i 落在下标 1。下标 0 前面没有数能配对，所以 i 从 1 起步。每到一个 i，就让内层 j 扫一遍它左边所有位置。
8. 10记录每个 i 处「公差→最长长度」这张表的列是结尾下标 i。每个 i 自带一本「公差→长度」的小账(哈希)，单个数起步长度都是 1。中间两行会显示当前正在算的那一对的公差和结果，末行汇总每列见过的最长。
9. 11d = 4 − 9 = −5第一对：i=1(值4)接 j=0(值9)。公差 −5。下标 0 那本账里没有 −5 的记录，说明 9 是开头(长度1)，接上 4 得 2。i=1 处最长更新成 2。
10. 12i 右移到下标 2(值7)外层 i 推进到下标 2(值7)。它左边有两个位置 0、1，内层 j 会挨个去配，各算一个公差。先看 j=0。
11. 13d = 7 − 9 = −2轮到 i=2(值7)，先配最左的 j=0(值9)。公差 −2，下标 0 没这个差，得长度 2(9→7)。i=2 处最长记为 2。
12. 14d = 7 − 4 = +3再配 j=1(值4)。公差 +3！这正是答案那条链的公差。下标 1 那本账里还没有 +3，所以 4 是这条 +3 链的开头，接上 7 得长度 2(4→7)。记牢 i=2 处有一笔「+3 → 2」，下面要用到它。
13. 15i 右移到下标 3(值2)i 推进到下标 3(值2)。它左边有三个位置，j 会依次配 0、1、2。盯着看值 2 能不能接上某条已有的链。
14. 16d = 2 − 9 = −7i=3(值2)登场，先配 j=0(值9)。公差 −7，新差，长度 2(9→2)。i=3 处最长记 2。
15. 17d = 2 − 4 = −2再配 j=1(值4)，公差 −2。下标 1 没这个差，长度 2(4→2)。i=3 处最长还是 2。
16. 18d = 2 − 7 = −5最后配 j=2(值7)，公差 −5。i=2 那本账里没有 −5(它只有 −2 和 +3)，所以长度 2(7→2)。i=3 全部配完，最长仍 2。值 2 是个「死胡同」，对答案没贡献。
17. 19i 右移到末位下标 4(值10)最后一列!i 到末位下标 4(值10)。它左边四个位置都要配。重点盯 j=2(值7) 那一对——前面 i=2 处存的「+3 → 2」马上派上用场。
18. 20d = 10 − 9 = +1最后的 i=4(值10)是决胜列。先配 j=0(值9)，公差 +1，长度 2(9→10)。i=4 处最长记 2。
19. 21d = 10 − 4 = +6再配 j=1(值4)，公差 +6，新差，长度 2(4→10)。还没碰到关键的那一对。
20. 22d = 10 − 7 = +3 命中已有链关键一击!配 j=2(值7)，公差 +3。回头查 i=2 那本账——里头正好存着「+3 → 2」(就是刚才 4→7 那条链)!于是 10 接上去：dp[4][+3] = 2 + 1 = 3。4→7→10 这条链终于拼成长度 3。
21. 23d = 10 − 2 = +8最后配 j=3(值2)，公差 +8，长度 2。它没能超过刚才的 3，所以 i=4 处最长稳定在 3。所有对都配完了。
22. 24答案 = 所有 dp 里的最大值 = 3看末行「i 处最长」：1、2、2、2、3，全局最大是 3，出现在 i=4。它对应的链就是高亮的 4、7、10。和示例答案 3 完全对上。
23. 254 → 7 → 10，公差 +3回头看这条绿链：下标 1、2、4 的 4、7、10，跳过 9 和 2，公差恒为 +3。DP 正是靠「每个数继承前面同公差的最长链」把它一节一节接出来的。
24. 26两层循环 i、j 共 O(n²) 对，每对只做一次哈希查改 O(1)，整体 O(n²)。关键就是「公差当哈希键」，让无穷多种公差各记各的账，互不打架。
25. 29公差 d = nums[i]−nums[j]，可正可负、范围可能很大(题目值域大时会爆)。哈希表只为真实出现过的公差开格子，省空间又不用做下标偏移。值域确定时也可以用 dp[i][d+offset] 的二维数组替代。
26. 31i=2 配 j=1 错算成 1如果 dp[1] 里没有 +3 时按 0 起算，dp[2][+3] 只得 1，等于把开头的 4 当成不存在。这样后面 10 接上来也只到 2，最终答案错成 2。正确是按 1 起算(4 自己长度 1)，才得 4→7=2、再到 4→7→10=3。

⚠️ 容易写错的地方

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

class Solution:
    def longestArithSeqLength(self, nums):
        n = len(nums)
        dp = [dict() for _ in range(n)]   # dp[i][d]=以i结尾、公差d的长度
        ans = 1
        for i in range(1, n):
            for j in range(i):
                d = nums[i] - nums[j]          # 公差
                dp[i][d] = dp[j].get(d, 1) + 1 # 接到j的同差链后
                ans = max(ans, dp[i][d])
        return ans

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        vector<unordered_map<int,int>> dp(n);  // dp[i][d]
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int d = nums[i] - nums[j];      // 公差
                int prev = dp[j].count(d) ? dp[j][d] : 1;
                dp[i][d] = prev + 1;
                ans = max(ans, dp[i][d]);
            }
        }
        return ans;
    }
};

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        Map<Integer,Integer>[] dp = new HashMap[n];  // dp[i][d]
        int ans = 1;
        for (int i = 0; i < n; i++) dp[i] = new HashMap<>();
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int d = nums[i] - nums[j];           // 公差
                int prev = dp[j].getOrDefault(d, 1);
                dp[i].put(d, prev + 1);
                ans = Math.max(ans, dp[i].get(d));
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问