2. 核心实现与状态转移原理2.1 状态定义为什么只需一个一维的哈希表动态规划题拿到手第一步永远是定义状态。这道题如果你按套路想成dp[i] 以数组中位置 i 结尾的最长定差子序列长度那就走偏了。因为子序列不要求连续位置 i 能接在谁后面取决于“值”而不是“下标”所以按下标做状态转移的时候还得回退扫描复杂度立刻回到 O(n^2)。正确的状态定义是dp[v] 以数值 v 作为结尾元素时能得到的最长定差子序列长度。这里 v 不包含具体下标只包含数值。这也是“最长定差子序列”比普通子序列题更友好的地方我们真正关心的只是最后一个数是多少前面在哪儿出现、以什么顺序出现只要最后一个数是 v它的最长长度就已经固定了。举个例子数组[1, 5, 7, 3, 8, 5]difference 2。我们一路扫描遇到 7 时我们知道以 7 结尾的最长定差子序列一定是从以 5 结尾的最长序列后面接上 7。如果前面出现过 5就去查dp[5]然后dp[7] dp[5] 1。遇到第二个 5 时以 5 结尾的最长序列可能比第一次遇到 5 时更长因为前面的 7 又更新过 3 之类所以dp[5]需要被更新而不是保留第一次的值。这就是为什么状态只需要一个 HashMap不需要二维数组也不需要把每个位置都存下来。因为对同一个值 v我们永远只需要保留它当前能达到的最大长度。后续再遇到 v要么用更大的长度覆盖要么保持不变绝不会出现“旧 v 比新 v 更优”的情况因为长度只增不减。这里有一个容易纠结的点如果同一个值出现多次而且后一次出现时它前面的那些元素位置更靠前怎么办答案是不影响。因为我们要的是最长长度后一次出现 v 时dp[v]已经被更新到当前最大了新来的 v 只要接上这个最大长度即可。别把“每个位置的序列”刻在脑子里只关注“以某个数结尾的最优长度”想通这一点状态转移就彻底顺了。2.2 转移方程推导其实就一行状态定好之后转移方程就非常简单。对于当前扫描到的数num它能形成的最长定差子序列只有两种情况如果num - difference这个值之前出现过说明当前num可以接到以num - difference结尾的最长序列后面那么长度就是dp[num - difference] 1。如果num - difference没出现过说明当前num只能自己作为起点长度就是 1。所以方程就是dp[num] dp.getOrDefault(num - difference, 0) 1一边扫描数组一边实时更新答案ans max(ans, dp[num])。整个过程只需要遍历一次数组每个元素的处理时间是 O(1)总时间复杂度 O(n)空间复杂度 O(n)。这个方程漂亮就漂亮在它不需要维护“每个长度的子序列最后一位是什么”也不需要二分查找因为差值固定前驱值也固定。你不需要在前面的序列里找一个“小于当前值且差值等于 difference”的数因为差值固定之后前驱就是唯一的num - difference。如果你熟悉最长递增子序列LIS会发现两者有本质不同。LIS 的前驱不唯一你需要在一堆候选状态里找最优所以要么 O(n²) 暴力要么用 patience sorting 优化到 O(n log n)。而这道题的前驱是恒定值直接用哈希表在 O(1) 时间内查询即可。所以这道题虽然也属于“子序列 DP”但它是最简单的那一档。提示如果 difference 是负数方程依然成立。比如 difference -2那么前驱就是num - (-2) num 2。程序里不用单独分正负讨论一行代码通吃。我第一次写的时候还傻乎乎地判断了方向后来发现根本没必要。2.3 和“最长连续序列”那道题的区别LeetCode 上有一道很经典的 128. Longest Consecutive Sequence也是用 HashMap 求解。但它要求的是连续序列而且差值是固定的 1且要求序列中的数在原数组中连续出现吗不对128 题要求的是“连续数值”的最长长度比如[100, 4, 200, 1, 3, 2]的最长连续序列是[1, 2, 3, 4]长度 4它不要求这些数在原数组中位置相邻也不要求是原数组的子序列只要这些数值构成连续的整数段就行。而 1218 是真正的子序列问题它要求这些数在原数组中的下标递增只是差值固定。两者看着像解法也看着像但一个查的是num - 1一个查的是num - difference一个要用 Set 去重并跳过不必要的枚举另一个直接遍历并用 HashMap 累计计数。如果你把 128 题的模板硬套到 1218 上很容易在去重和枚举起点的地方出问题。所以看到“哈希表 序列”别急着套模板先想清楚这个序列在原数组中有没有顺序要求差值是固定值还是任意值如果是有序要求且差值固定那 1218 的思路就是最优解。3. 完整代码实现与关键循环逐行拆解3.1 Java标准解法耗时约99ms的写法我日常刷题用 Java 居多贴一份我实测耗时在 99ms 左右、内存约 55MB 的写法。这个成绩在 LeetCode 的 Java 提交里属于比较靠前的水平。class Solution { public int longestSubsequence(int[] arr, int difference) { // key: 数值value: 以该数值结尾的最长定差子序列长度 MapInteger, Integer dp new HashMap(); int ans 0; for (int num : arr) { int prevLength dp.getOrDefault(num - difference, 0); int curLength prevLength 1; dp.put(num, curLength); if (curLength ans) { ans curLength; } } return ans; } }别小看这几行里面有些细节值得说道说道。getOrDefault(num - difference, 0)是这道题的灵魂。它把“前驱是否存在”和“如果存在就取值”合二为一少写一个if。如果前驱不存在默认 0加 1 之后就等于 1完美对应“当前数作为序列起点”的情况。dp.put(num, curLength)是无条件覆盖。对同一个值 num后出现的长度一定不小于之前记录的长度所以覆盖是安全的。这里不需要max比较因为curLength本身就是基于当前最新状态算出来的。答案在循环内实时更新不用等遍历完再遍历一遍 HashMap。我提交过几个版本发现一个有趣的性能点如果用HashMapInteger, Integer的默认容量耗时稳定在 99ms 左右如果预先指定容量比如new HashMap()耗时基本不变但如果你用new HashMap(arr.length * 2)在某些测试用例上会稍快一点大概 92ms 左右。原因是减少了 resize 次数但也会浪费一些内存。整体差异不大面试和笔试场景没必要过度优化。这里顺带提一下 Java 的 Integer 缓存问题。当difference的绝对值很大时num - difference得到的新 Integer 对象不会走缓存但 HashMap 底层用的是hashCode()和equals()跟对象是否缓存无关所以不会有任何 bug。只不过如果你想用MapInteger, Integer的computeIfAbsent写法消耗会更大一些我实测会慢 10ms 左右所以不推荐在这种固定差值场景用它。3.2 Python、Go 等语言的实现要点对比Python 版几乎是 Java 的直译但有一个很关键的性能点用普通 dict 代替defaultdict可能会更稳定。因为defaultdict在访问不存在的 key 时会自动插入默认值这会导致 dict 不断膨胀而且语义上和get不同容易踩坑。class Solution: def longestSubsequence(self, arr: List[int], difference: int) - int: dp {} ans 0 for num in arr: length dp.get(num - difference, 0) 1 dp[num] length ans max(ans, length) return ansPython 这段代码在 LeetCode 上的耗时一般稳定在 300ms 左右。因为 Python 的 dict 虽然快但解释器开销摆在那里。如果你在本地跑更大规模的数据可以考虑用collections.Counter但实测和 dict.get 差别不大。记住一点别用defaultdict(int)写这道题因为dp[num - difference]会自动创建 key 并写入 0导致 dict 变大变慢语义也不直观。Go 版本的思路同样直接用map[int]intfunc longestSubsequence(arr []int, difference int) int { dp : make(map[int]int, len(arr)) ans : 0 for _, num : range arr { length : dp[num-difference] 1 dp[num] length if length ans { ans length } } return ans }注意Go 的 map 在访问不存在的 key 时会返回零值所以dp[num-difference]自动为 0不用手动做默认值处理。这是 Go 写这道题比 Java 更省事的地方。make(map[int]int, len(arr))预先分配容量能明显减少扩容带来的性能损耗实测大数据量下比不预分配快不少。3.3 为什么不能先把数组排序或去重新手很容易想到先排序再 DP因为“序列”这个词容易让人联想到“有序数组”。但这里有个致命的坑子序列要求保持原数组中的相对顺序。排序会把原始顺序打乱导致错误的答案。举个例子arr [3, 5, 1]difference 2。正确答案是 2因为子序列[3, 5]满足差值 2。如果先排序得到[1, 3, 5]动态规划会得到[1, 3, 5]这个长度为 3 的序列看起来更“长”但实际上在原数组里 1 出现在 3 和 5 之后不能作为它们的前驱所以答案是错的。那能不能去重呢也不能直接去重。因为同一个数值可能出现在不同位置如果你只保留一次会丢失“重复数值可以延长序列”的机会。不过好在 HashMap 的覆盖机制天然处理了这种情况——同一个值出现多次dp里永远保存最大的那个长度所以不需要手动去重。排序和去重这两条路都是把“子序列”和“子集”混淆了。子序列强调的是下标顺序和值的大小顺序无关。所以这道题的遍历方向必须是原数组从左到右不能重排。注意如果你把题目换成“最长定差子集”即不要求原数组顺序那排序后 DP 反而是更经典的做法。但题目一旦强调 subsequence顺序就是底线动不得。4. 常见错误与性能优化坑排查实录4.1 误用最长递增子序列的模板我在各种题解评论区看到最多的错误就是用传统的 LIS 写法去套这道题。大致长这样int[] dp new int[arr.length]; Arrays.fill(dp, 1); for (int i 0; i arr.length; i) { for (int j 0; j i; j) { if (arr[i] - arr[j] difference) { dp[i] Math.max(dp[i], dp[j] 1); } } }这个写法本身逻辑没有错它确实能找到最长定差子序列但是时间复杂度是 O(n²)。当arr.length接近 10^5 时10^10 次操作在 LeetCode 上必然超时。这就是为什么很多人觉得“思路明明对的啊为什么过不了”。我建议你把这种 O(n²) 的写法当作“暴力验证版”只在本地小数据集上用来对拍测试千万不要直接提交。用哈希表把第二层循环优化掉核心思路就是既然差值固定前驱值唯一那我为什么要遍历所有 j 呢直接去 HashMap 里查arr[i] - difference不就行了。如果你在面试中写暴力解面试官大概率会追问“能不能优化”这时候你把 HashMap 方案写出来同时讲清楚两种写法的时间和空间差异基本就能过关。4.2 用数组代替HashMap的可行性和边界分析有的题目数值范围很小比如 0 到 10000可以用数组代替 HashMap 来提升性能。这道题给的数值范围是多少呢-10^4 arr[i] 10^4差值范围-2*10^4 difference 2*10^4。那么num - difference的范围大约是-3*10^4到3*10^4看起来用数组也可以理论上是可行的把数组偏移一下就行。比如开一个长度为 70000 的数组下标从 0 开始实际值 下标 - 35000。但有两个问题数组需要处理负数下标得手动做偏移代码可读性变差。数组大小直接取决于数值范围一旦题目偷偷把数值范围扩大数组方案就崩了。所以我建议直接用 HashMap。虽然常数时间比数组略慢但通用性强代码也更优雅。只有当数据范围极小比如 0 到 100且追求极致性能时才考虑用数组模拟哈希表。这里也想提一个真实的性能对比我用数组偏移法写了一遍耗时大概在 45ms 左右比 HashMap 的 99ms 快了一倍。但在实际工程或面试里这点性能差异远不如代码的可维护性和通用性重要。刷题求快可以用数组写项目千万别这么干。4.3 关于“耗时99ms”的优化心得标题里提到“耗时99”这其实是我提交记录里的一个真实数字。LeetCode 上 Java 提交的耗时分布最快的大概在 40ms 左右中位数在 100-150ms 之间99ms 已经是比较理想的状态。但说实话在 LeetCode 上刷题耗时只是一个参考指标不同语言、不同硬件、不同的并发负载都会影响这个数字。同一份代码同一个用例多提交几次误差可能达到 20ms 甚至更多。所以别太纠结“为什么别人的代码跑了 60ms我的跑 100ms”先看复杂度级别对不对。不过如果你想尽量缩短耗时有几个稳定有效的小技巧使用getOrDefault而不是先containsKey再get减少一次哈希查找。避免在循环里反复调用类似于Math.max(ans, length)这种方法虽然 Java 的 JIT 会内联但显式 if 比较更直接。如果你确定这个测试用例数组很长预先初始化 HashMap 容量可以减少 resize但别初始化得太大否则内存浪费严重。能不用computeIfAbsent就不用它的函数式接口调用开销在这个场景下是实实在在的。我试过把ans从循环里挪出去等遍历完再遍历 HashMap 取最大值结果耗时反而变长了。因为 HashMap 的遍历也需要时间而且在循环里维护一个变量CPU 缓存命中率更高。所以“实时更新 ans”不仅是写法最简单的也是性能最好的。4.4 经典边界用例测试与自检清单写完代码之后我建议你用下面这组用例自测一遍能覆盖绝大多数边界情况输入: arr [1, 2, 3, 4], difference 1 输出: 4 整个数组本身就是等差序列 输入: arr [1, 3, 5, 7], difference 1 输出: 1 相邻差值不是 1只能取单个元素 输入: arr [1, 5, 7, 8, 5, 3, 4, 2, 1], difference -2 输出: 4 存在递减序列 7, 5, 3, 1 输入: arr [1, 1, 1, 1], difference 0 输出: 4 差值 0 表示所有相同元素都能连成序列 输入: arr [1], difference 100 输出: 1 单个元素本身就是长度为 1 的序列其中difference 0的场景最容易写错。此时num - difference num代码会执行dp.put(num, dp.getOrDefault(num, 0) 1)效果就是把每个值的出现次数累计起来。所以输入[1, 1, 1, 1]会输出 4完全符合“定差为 0”的定义。如果你写的代码在差值 0 时只能输出 1说明你把“序列起点”和“继承前驱”的逻辑搞混了赶紧回去检查getOrDefault的默认值。5. 复杂度分析的深层理解与变体思考5.1 时间空间复杂度真的是 O(n) 吗从代码来看每个元素只处理一次HashMap 的 get/put 在平均情况下是 O(1)所以时间复杂度是 O(n)。空间复杂度上HashMap 最多存储多少个 key注意不是 n而是数组中不同数值的个数最坏情况下每个元素的值都不同那就是 O(n)。但等一下HashMap 的理论复杂度是 O(1)但在哈希冲突严重时可能退化。比如题目故意构造一堆相同的 key或者hashCode()分布极差HashMap 可能退化到 O(n) 的查找。好在这道题的测试数据不会刻意构造这种攻击而且 Java 8 之后的 HashMap 在链表长度超过 8 时会转成红黑树最坏复杂度也能保证 O(log n)。所以更严谨的说法是平均时间复杂度 O(n)最坏 O(n log n)但实际刷题场景中完全可以当作 O(n) 对待。如果你在面试里被问到“有没有可能退化”能把红黑树这个点说出来面试官会觉得你有深度。5.2 简单变体装进 Map 里的扩展思路如果把题目变一下不给你固定的 difference而是让你求任意差值的最长等差子序列那就变成经典的 1027. Longest Arithmetic Subsequence。那个题就不能用一维 HashMap 了因为同一个值可能对应多个不同差值你需要定义dp[i][diff]或者用嵌套 MapMapInteger, MapInteger, Integerkey 是差值value 是长度。思路是对于每个位置i遍历它之前的所有位置j计算差值diff arr[i] - arr[j]然后更新dp[i][diff] dp[j][diff] 1。复杂度 O(n²)。这道题之所以难就是因为差值不固定你没法用一个固定的num - difference去哈希查找。另外还有一个变体定差子数组连续。如果题目改成“最长的连续子数组且相邻差值为 difference”那就是滑动窗口或者一维 DP 的题目直接判断arr[i] - arr[i-1] difference并累计长度即可反而更简单。把 1218 和这些变体放在一起对比你会发现核心区别就一个前驱是否唯一。前驱唯一时用 HashMap 做 O(n) 的“接力赛”前驱不唯一时只能退化到 O(n²) 的“多路搜索”。理解了这一点做题层次就不一样了。5.3 从这道题延伸出的刷题顺序建议如果你正在准备面试或者刚开始刷动态规划我给一个顺手的练习路线先做 300. Longest Increasing Subsequence理解经典的 O(n²) DP 和 O(n log n) 优化这是子序列问题的地基。再做 128. Longest Consecutive Sequence理解哈希表如何优化“固定前驱”的枚举。然后做 1218把有限状态机的思维带进来前驱唯一状态方程一行搞定。进阶做 1027感受差值不固定时状态维度的爆炸式增长。最后可以做 873. Length of Longest Fibonacci Subsequence它是“双前驱”的哈希表动态规划能帮你真正掌握“用哈希表替代遍历找前驱”这个套路。这条路线走下来你对“子序列 哈希表优化”这类题的敏感度会明显提升。至少再看到定差、定和、斐波那契式子序列时不会一头雾水。6. 写在最后的个人实操体会这道题我第一次做的时候其实卡在最开始的状态定义上。脑子里一直在想“以 i 结尾的 dp 数组”怎么写转移结果发现怎么都要回退扫描复杂度降不下来。后来看了一眼题解区看到有人直接用 Map 存数值对应的长度瞬间就通了。我自己复盘过之所以会走弯路是因为惯性思维太重。子序列 DP 不一定都要用“以下标为状态”当转移条件只和值有关和下标无关时用值做状态往往更简洁。判断“能不能用值做状态”的方法很简单看状态转移时需不需要知道当前元素的前驱具体在哪个位置。如果不需要只用知道“某个值存不存在/最长长度是多少”那就可以用哈希表。实际写代码时还有一个细节我在本地测试大数组时发现如果用int[] arr作为输入Java 的for-each循环比传统的for (int i 0; i arr.length; i)通常略快一点因为省去了下标寻址和数组边界检查其实这句有点争议JIT 编译后两者差距不大但 for-each 确实更简洁我就一直用 for-each 了。最后再多说一句如果你提交的时候遇到“Time Limit Exceeded”先别急着优化常数先确认复杂度到底是 O(n) 还是 O(n²)。很多人写的 HashMap 代码一眼看过去是 O(n)但细看循环里嵌套了遍历 HashMap 的代码复杂度就变了。这道题最关键的就是保证每个元素只处理一次别在循环里再做二次遍历。这个题做完你再去看 1027 或者 873会有一种“咦这不就是把一个 Map 换成两层 Map 的事吗”的感觉。刷题的乐趣就在这里——当你掌握了某个思维模型之后新题蜜变成了旧题的变体。