最长定差子序列 图解题解

定差子序列这道题到底要挑出什么

给数组 arr 和固定整数 difference，在 arr 里找最长的子序列，要求相邻两项差恰好是 difference，可跳着取但保持原顺序。以 arr=[1,5,7,8,5,3,4,2,1]、difference=−2 为例，隔着别的数挑出 7、5、3、1，每步减 2，长度 4 就是答案。公差直接给死，问题就是沿固定步长最长能串几个数。

为什么每个数往后凑一条链会 O(n²)

顺手的想法是拿每个数当起点，反复往后找「当前值加 difference」凑一条链。但每个起点都要往后扫一遍，n 个起点就是 O(n²)，多条链还反复重算。普通最长递增子序列（LIS，最长的逐个变大的子序列）也一样：每个位置都要往前扫所有更小的数，逃不掉 O(n²)。反过来做：扫到一个数，只回头看它的前一项在不在。

dp 的下标为什么用数值而不用数组位置

定义 dp[v] 表示以数值 v 结尾的最长定差子序列有多长，下标是数值本身、不是它在数组里的位置。道理在公差固定：v 接在谁后面唯一确定——前一项 p 满足 v − p = difference，即 p = v − difference，只有这一个值能当前驱。既然「v 接谁」只由数值决定、和排第几无关，就把每个值当键塞进哈希表（拿「值」一步查到记录、不挨个找的表），一步查到前驱。公差不定的题前驱不唯一，只好用 dp[下标][公差] 两维硬记。

前驱查得到和查不到各怎么办

转移式（由前面算好的值推出当前值的式子）就一行：dp[v]=dp.get(v−difference,0)+1。扫到 v，查前驱 v−difference 当前的 dp 值：查得到就在那条链上长度加一；查不到，v 自己当开头，长度是 0+1=1（不是 1+1，最易写错）。从左往右扫为什么天然对：前驱在 v 左边出现过就早写进表、查得到；没出现就另起一条，继承的一定是左边那条链，顺序自动满足。还有个坑：同一个值再次出现直接覆盖旧 dp。

拿题面这组数把 dp 一路查出来

difference=−2 时前驱是 v+2，逐个扫。前四个数 1、5、7、8 的前驱 3、7、9、10 都不在表里，各自 dp=1。再遇值 5 查 dp[7]=1，dp[5]=2，链 7→5；值 3 查 dp[5]=2，dp[3]=3，链 7→5→3；值 4 前驱 6 不在，dp[4]=1；值 2 查 dp[4]=1，dp[2]=2，短旁支；末尾值 1 查 dp[3]=3，dp[1] 覆盖成 4，主链 7→5→3→1 拼齐。扫完取最大值 4，对上示例。

复杂度为什么是 O(n)，difference 为 0 会不会崩

数组扫一遍，每个数一次哈希查加一次写、均摊 O(1)（均摊=偶尔慢一下、平均每次仍是常数），时间 O(n)；dp 表最多存 n 个不同值，空间 O(n)，赢在前驱唯一。两个边界：前驱方向别算反，前一项是 v−difference 不是 v+difference，公差为负时前驱反而比 v 大；difference=0 时前驱是 v 自己，相同值接成一条链，[1,1,1] 答案是 3，代码不用特判。

Python

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

C++

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

Java

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