最长等差数列

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

暴力枚举公差再逐个匹配，慢且乱。换个视角：固定以某个数结尾，再问「它前面哪个数能接上来」，这就有了 DP 的味道。

对每个 i，枚举它前面的 j：公差 d = nums[i] − nums[j]。那么把 nums[i] 接到「以 nums[j] 结尾、同样公差 d」的串后面，长度 +1。公差用哈希表当下标，多少种差都装得下。

若 j 那里本来没有公差 d 的记录，说明 nums[j] 是这串的开头，按长度 1 起算，接上 nums[i] 就是 2。下面用示例 [9,4,7,2,10] 一对一对地填这张表。

看清这个数组：下面这排是原数组，格子下方的小数字是下标 i。算法外层循环让 i 从 1 走到 4，内层让 j 扫遍 i 左边所有位置，逐对算公差。

目标先剧透：提前把答案点出来：绿色的三个数 4、7、10(下标 1、2、4)隔着 9 和 2 取出来，两两差 +3。接下来看 DP 怎么把这条链一格一格拼出来。

外层指针就位：正式开扫。外层 指针 i 落在下标 1。下标 0 前面没有数能配对，所以 i 从 1 起步。每到一个 i，就让内层 j 扫一遍它左边所有位置。

建表 · dp 按结尾下标统计：这张表的列是结尾下标 i。每个 i 自带一本「公差→长度」的小账(哈希)，单个数起步长度都是 1。中间两行会显示当前正在算的那一对的公差和结果，末行汇总每列见过的最长。

i=1 · 配 j=0：第一对：i=1(值4)接 j=0(值9)。公差 −5。下标 0 那本账里没有 −5 的记录，说明 9 是开头(长度1)，接上 4 得 2。i=1 处最长更新成 2。

i=2 入场：外层 i 推进到下标 2(值7)。它左边有两个位置 0、1，内层 j 会挨个去配，各算一个公差。先看 j=0。

i=2 · 配 j=0：轮到 i=2(值7)，先配最左的 j=0(值9)。公差 −2，下标 0 没这个差，得长度 2(9→7)。i=2 处最长记为 2。

i=2 · 配 j=1 · 链开始长出来：再配 j=1(值4)。公差 +3！这正是答案那条链的公差。下标 1 那本账里还没有 +3，所以 4 是这条 +3 链的开头，接上 7 得长度 2(4→7)。记牢 i=2 处有一笔「+3 → 2」，下面要用到它。

i=3 入场：i 推进到下标 3(值2)。它左边有三个位置，j 会依次配 0、1、2。盯着看值 2 能不能接上某条已有的链。

i=3 · 配 j=0：i=3(值2)登场，先配 j=0(值9)。公差 −7，新差，长度 2(9→2)。i=3 处最长记 2。

i=3 · 配 j=1：再配 j=1(值4)，公差 −2。下标 1 没这个差，长度 2(4→2)。i=3 处最长还是 2。

i=3 · 配 j=2：最后配 j=2(值7)，公差 −5。i=2 那本账里没有 −5(它只有 −2 和 +3)，所以长度 2(7→2)。i=3 全部配完，最长仍 2。值 2 是个「死胡同」，对答案没贡献。

i=4 入场 · 决胜列：最后一列!i 到末位下标 4(值10)。它左边四个位置都要配。重点盯 j=2(值7) 那一对——前面 i=2 处存的「+3 → 2」马上派上用场。

i=4 · 配 j=0：最后的 i=4(值10)是决胜列。先配 j=0(值9)，公差 +1，长度 2(9→10)。i=4 处最长记 2。

i=4 · 配 j=1：再配 j=1(值4)，公差 +6，新差，长度 2(4→10)。还没碰到关键的那一对。

i=4 · 配 j=2 · 决胜一击!：关键一击!配 j=2(值7)，公差 +3。回头查 i=2 那本账——里头正好存着「+3 → 2」(就是刚才 4→7 那条链)!于是 10 接上去：dp[4][+3] = 2 + 1 = 3。4→7→10 这条链终于拼成长度 3。

i=4 · 配 j=3：最后配 j=3(值2)，公差 +8，长度 2。它没能超过刚才的 3，所以 i=4 处最长稳定在 3。所有对都配完了。

填表完成 · 取全局最大：看末行「i 处最长」：1、2、2、2、3，全局最大是 3，出现在 i=4。它对应的链就是高亮的 4、7、10。和示例答案 3 完全对上。

回放答案链：回头看这条绿链：下标 1、2、4 的 4、7、10，跳过 9 和 2，公差恒为 +3。DP 正是靠「每个数继承前面同公差的最长链」把它一节一节接出来的。

两层循环 i、j 共 O(n²) 对，每对只做一次哈希查改 O(1)，整体 O(n²)。关键就是「公差当哈希键」，让无穷多种公差各记各的账，互不打架。

公差 d = nums[i]−nums[j]，可正可负、范围可能很大(题目值域大时会爆)。哈希表只为真实出现过的公差开格子，省空间又不用做下标偏移。值域确定时也可以用 dp[i][d+offset] 的二维数组替代。

雷区实演 · 把开头按 0 起算：如果 dp[1] 里没有 +3 时按 0 起算，dp[2][+3] 只得 1，等于把开头的 4 当成不存在。这样后面 10 接上来也只到 2，最终答案错成 2。正确是按 1 起算(4 自己长度 1)，才得 4→7=2、再到 4→7→10=3。

边界三连：注意「全相同」公差为 0 也合法，三个 7 是长度 3 的等差数列。任意两个数也必成等差，所以答案至少是 min(n,2)(n≥2 时)。

面试追问：把「公差为什么必须进状态」讲透是这题的核心得分点，再补一句值域已知时可用数组替哈希，体现你懂权衡。