最长定差子序列

可以，但那样对每个起点都要往后扫一遍，最坏 O(n²)。我们想要一遍扫完。换个角度想：与其往后找，不如往回看「我的前一项在没在」。

对每个数当起点，反复在后面找「当前值 + difference」，凑出一条链。多个起点的链会大量重算，整体 O(n²) 甚至更糟。我们要把「往后找」翻转成「往回查一次」。

注意这里 dp 的下标是数值本身，不是数组位置。因为公差固定，一个数 v 能接到谁后面是唯一确定的——只能接在值为 v − difference 的那个数后面。

扫到 v 时，去查它的前驱 v−difference 当前的 dp 值：查得到就 +1 接上去，查不到就说明 v 是新链的开头(长度 1)。前驱要是已经在 v 左边出现过就在表里、查得到；还没出现就查不到、让 v 自己开新链——所以从左往右扫天然满足顺序。下面用 difference = −2，前驱就是 v+2。

看清这个数组：这排是原数组，格子下方小数字是下标。公差固定为 −2，意味着 v 只能接在值 v+2 的数后面。下面下方会出现一张哈希表 dp{值→长度}，随扫描一格格长出来。

目标先剧透：提前剧透答案：绿色的 7、5、3、1(下标 2、4、5、8)隔着别的数取出来，两两差 −2。接下来看 dp 怎么从左到右把这条链一节一节接出来。

i=0 值1 · 查前驱：第一个数 值1(下标0)。先算前驱 1+2=3，去 dp 表里查——表还空着，查不到 3。

i=0 值1 · 写入：没查到前驱 → 1 自己是开头，dp[1]=1。dp 表里新增一行「1 → 1」(绿色高亮的就是刚写入的)。

i=1 值5 · 查前驱：值5(下标1)。前驱 7，但 7 在更右边还没扫到，dp 表里查不到。

i=1 值5 · 写入：查不到 7 → 5 暂时也是开头，dp[5]=1。表里多一行「5 → 1」。

i=2 值7 · 查前驱：值7(下标2)。前驱 9 不存在。别小看现在的 7，它正是答案链的头。

i=2 值7 · 写入：写入 dp[7]=1，新增「7 → 1」。记牢这行——后面 5、3、1 会一节节接到它后面。

i=3 值8 · 查前驱：值8(下标3)。前驱 10 不存在，8 是个对答案没用的旁支。

i=3 值8 · 写入：dp[8]=1，照记「8 → 1」。算法一视同仁，不管是不是答案链。

i=4 值5 · 查前驱 · 命中!：又见 值5(下标4)。前驱 7 这次命中了(蓝色高亮那行 dp[7]=1)! 数组里下标2 的 7 也点亮了——5 能接到它后面。

i=4 值5 · 写入 · 覆盖：dp[5] = 1+1 = 2。原来的「5 → 1」被覆盖成「5 → 2」(同一个值只留最长)。链 7→5 拼成长度 2。

i=5 值3 · 查前驱 · 命中!：值3(下标5)。前驱 5 命中，且 dp[5] 已经是 2(那条 7→5 链)! 3 能接到这条更长的链后面。

i=5 值3 · 写入 · 链长到3：dp[3] = 2+1 = 3，新增「3 → 3」。链变成 7→5→3，长度 3。一节一节接出来了。

i=6 值4 · 查前驱：值4(下标6)。前驱 6 从没出现过，又是一条新开头。

i=6 值4 · 写入：dp[4]=1，新增「4 → 1」。4 也是旁支，对最长链没贡献。

i=7 值2 · 查前驱 · 命中：值2(下标7)。前驱 4 命中，dp[4]=1。2 能接到 4 后面，但这只是条短旁支。

i=7 值2 · 写入：dp[2] = 1+1 = 2，新增「2 → 2」。这条 4→2 旁支长度才 2，比不过主链的 3。

i=8 值1 · 查前驱 · 决胜命中!：最后的 值1(下标8)! 前驱 3 命中，而 dp[3]=3(就是那条 7→5→3)! 数组里下标5 的 3 也点亮——1 要接到主链尾巴。

i=8 值1 · 写入 · 决胜一击!：dp[1] = 3+1 = 4! 开头那行「1 → 1」被覆盖成「1 → 4」。主链 7→5→3→1 终于拼成长度 4!

扫描完成 · 取全局最大：全扫完了，看 dp 表里的最大值：4(来自 dp[1])。它对应的链就是高亮的 7→5→3→1，下标 2、4、5、8。和示例答案 4 完全对上。

回放答案链：回放这条绿链：下标 2、4、5、8 的 7、5、3、1，跳过中间的数，公差恒为 −2。dp 正是靠「每个数只查唯一前驱 v−difference」一节一节接出来的——一遍扫完，干净利落。

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

因为公差固定时，「v 该接谁」只由数值决定(接值为 v−difference 的那个)，和它在哪个下标无关。用数值当键，查前驱一步到位。1027 公差不定，才要 dp[下标][公差] 两维。

雷区实演 · 前驱方向算反：如果把前驱错算成 v−difference 又把 difference 当 +2，扫到 5 时会去查 dp[3](不存在)，结果 5 接不到前面的 7，主链断在第一节，答案错成 1。正确是查 5−(−2)=7，命中 dp[7]=1 才接得上。

边界三连：特别注意 difference=0 的情况：前驱就是 v 自己，相同的值能一个接一个，所以 [1,1,1] 答案是 3。代码无需特判，dp[v]=dp[v-0]+1 自然处理。

面试追问：把「公差固定 → 前驱唯一 → 降到一维 O(n)」这条主线讲清，再点出和 1027 的区别，是这题的核心得分点。