最长等差数列 图解题解

最长等差数列这道题到底要挑出什么

给一个整数数组 nums，挑出最长的等差子序列、返回长度。子序列（跳着挑但保持原顺序的一串）不必连续，等差要求相邻两项之差处处相等，这个差叫公差。题面 nums=[9,4,7,2,10] 答案 3：取出 4、7、10（隔着 9 和 2），两两差 +3。

公差没给，为什么挨个去试会又慢又乱

公差可正可负、值域一大就近乎无穷种，先枚举公差再回数组凑链，得把所有差各扫一趟，还大量重复重算。固定「以某个数结尾」，只问前面哪个数能接上来，把算好的链长记下复用，就是动态规划（把『以某数结尾、某公差的最长链』算一次记下、后面直接取），指数级乱试便压成两层循环的递推。

公差进不了普通下标，怎么让它当状态（要盯住哪几个量）的一部分

假如公差给定，这题就退化成「固定差值的最长子序列」，一趟扫描能解；它没给。于是把公差塞进状态：定义 dp[i][d]（以下标 i 结尾、公差为 d 的最长等差子序列有多长）。公差有无穷多种、整数下标装不下，就用哈希表（按键存值、查改都快的表）存，公差当键、链长当值。每个下标 i 各挂一张小表，只为出现过的公差开格子。

接到前面同公差的链上，长度为什么正好加 1

算 dp[i][d] 时定 nums[i] 当结尾，看前面某个 nums[j]，两者之差 d=nums[i]−nums[j] 就是公差。把 nums[i] 接到「以 nums[j] 结尾、同差 d」的最长链尾上，长度加 1，即 dp[i][d]=dp[j][d]+1。若下标 j 的账里没有 d，nums[j] 就是这条 d 链的开头（长度 1），接上得 2，参考代码 dp[j].get(d, 1) 的默认值 1 正好收了这情况。公差固定后，只要 nums[j] 那条同差链最长，接上仍最长。

拿 [9,4,7,2,10] 亲手把这几本小账填一遍

排开 nums=[9,4,7,2,10]（下标 0 到 4），各备空账、ans 从 1 起。下标 1 的 4 回看 9：公差 −5，dp[1][−5]=2。下标 2 的 7：配 9 得 −2、配 4 得 +3，各长度 2，账里从此有「+3 → 2」。下标 3 的 2 配出的三个差全是新差、接不长。下标 4 的 10：配 9 得 +1、配 4 得 +6 都只 2；配 7 公差 +3，回头查下标 2 正存着「+3 → 2」，dp[4][+3]=2+1=3。各下标最长 1、2、2、2、3，全局取 3，对应 4→7→10，和答案 3 对上。

找不到公差就按 0 起算，答案为什么会整整缩水 1

把 get 的默认值写成 0，dp[1][−5] 就成了 0+1=1，往后每条链都比真相少 1 节，示例从 3 缩成 2。根子在默认值的含义：nums[j] 自己就是长度 1 的起点，找不到同差前驱时该按 1 起算，而非 0。

复杂度上，两层循环共 n²/2 对、每对一次哈希查改，时间 O(n²)（大 O 记号，描述规模变大时操作数怎么涨）；每个下标存前面那些公差，空间也是 O(n²)。两处别弄错：公差 0 也合法，三个相同的 7 是长度 3 的等差数列；ans 初值给 1，单个数就是长度 1 的等差数列。

Python

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

C++

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;
    }
};

Java

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;
    }
}