先说个题外话。力扣 Hot 100 里的题大部分是“你刷过就会没刷过就卡”的类型最长连续序列就是其中很有代表性的一道。这题表面上是哈希表实际上考的是“你怎么想到用哈希表去避免重复计算”这个思维模式。我第一次刷这题的时候第一反应是排序写完跑通还觉得挺简单结果一看题目要求 O(n)人傻了。后来把哈希解法吃透才发现这题的精华根本不在 HashSet 的 API 上而在那个“只从序列起点开始统计”的设计上。这篇文章我就用 Java 把这题从头拆到尾包括最开始的错误直觉、哈希解法的核心思路、代码里容易踩的细节以及面试官会顺着这个问题往下追问的变体。不管你是刚开始刷 Hot 100还是准备跳槽面试这篇都能给你一点参考。1. 题目到底在问什么以及为什么第一直觉往往是错的1.1 读懂题目里的“连续”到底是什么意思题目给定一个未排序的整数数组要求找出数字连续的最长序列的长度。这里的“连续”是数值上的连续不是位置上的连续。举个例子数组[100, 4, 200, 1, 3, 2]里面有一串 1、2、3、4它们是数值上连续的长度为 4 的序列即使这 4 个数字在数组里的位置是散落的。这也是题目最容易迷惑人的地方。很多人一看到“最长连续”脑子里浮现的是“找最长连续递增子数组”那种题比如[1, 2, 3, 2, 4]里的连续段只有[1,2,3]长度是 3。但这道题不一样它不要求元素在原数组里的相对顺序也不要求子数组的连续性只看“值在不在数组里”。所以这题的核心可以翻译成一句话给你一堆数你只关心这些数的值本身找出数值上能连成最长的一条线有多长。这个翻译一旦到位哈希表就自然而然浮出来了——因为“某个数在不在数组里”就是哈希集合最擅长的查询。1.2 暴力解法和排序解法的复杂度陷阱顺着直觉想最容易想到的暴力方案是枚举每个数字 x然后查 x1、x2、x3……在不在数组里直到断开记录长度。这个方案如果用数组线性查找复杂度会来到 O(n^3)连 LeetCode 的小数据都过不了。哪怕你优化成用 HashSet 存所有数字把单次查找降到 O(1)如果对每个数字都往上延伸查找最坏情况是数组恰好是[1, 2, 3, ..., n]这种完整连续区间第一个元素 1 就要执行 n 次查找之后的每一个元素也各自执行 n-1、n-2……次整体复杂度依然回到 O(n^2)超时没商量。排序解法也很自然Arrays.sort(nums)然后从左到右遍历判断相邻两个数差值是否为 1是就把当前长度加 1不是就重置。这个写法我在初学阶段经常用而且它确实能过不少测试用例。但它的复杂度是 O(n log n)在题目明确要求 O(n) 的前提下从理念上就站不住脚。LeetCode 的测试数据有时候不会把排序方案的耗时差距拉得很大所以会出现“排序也过了”的情况但这不代表解法正确。如果你在面试里写出排序方案面试官下一句话一定是“能不能 O(n)”到时候再临时改思路手忙脚乱的概率很高。1.3 我最初交过的一份“能过但不对”的代码说个真实经历。我最初写这题用的就是排序加遍历代码很短public int longestConsecutive(int[] nums) { if (nums.length 0) return 0; Arrays.sort(nums); int longest 1; int current 1; for (int i 1; i nums.length; i) { if (nums[i] nums[i - 1]) { continue; } else if (nums[i] nums[i - 1] 1) { current; } else { longest Math.max(longest, current); current 1; } } return Math.max(longest, current); }这代码本地测试各种用例都没问题提交也过了。但后来我看了一下这道题的讨论区才发现题目要求的是 O(n)。我当时觉得“既然能过是不是说明题目的数据不够强”直到有人点醒我解法的时间复杂度是否满足要求不以测试数据强度为转移这是衡量算法能力的基本标准。从那以后我再也不敢拿“能过”当作“正确”的挡箭牌了。2. 核心思路从“起点”入手让每个序列只被统计一次2.1 关键观察连续序列的最小值是唯一需要枚举的对象哈希解法的核心来自一个非常简单的观察。假设数组里有这样一串连续的数值x、x1、x2、……、xk。这条连续序列的长度是 k1。如果你从中间任何一个数字开始往上数比如从 x1 开始数你会把属于同一条序列的一部分重新数一遍。如果从 x 开始数你会完整数到 k1。但如果从 x2 开始数你又会重复数到一个已经属于这条序列的片段。所以思路就应该反过来每个连续序列只允许从它的最小值开始数一次。怎么判断当前数字是不是最小值只需要检查它的前一个数num - 1是否存在。如果存在说明当前数字只是某条连续序列里的中间节点或末尾节点从它开始数只会重复劳动直接跳过。如果num - 1不存在说明当前数字是一条连续序列的起点这时候再用 while 循环一路往大数方向数直到断掉。这个判断是整个算法的灵魂。它不复杂但你要在纸上推演几遍才能真正理解为什么能保证“只统计一次”。2.2 用题目示例完整走一遍流程拿标准示例[100, 4, 200, 1, 3, 2]来说。先把所有数字放进一个 HashSet得到{100, 4, 200, 1, 3, 2}。遍历集合数字 100contains(99)为 false说明 100 是一个序列起点。开始 whilecontains(101)为 false断掉。长度 1。最长更新为 1。数字 4contains(3)为 true跳过。数字 200contains(199)为 false是起点。whilecontains(201)为 false长度 1。最长还是 1。数字 1contains(0)为 false是起点。whilecontains(2)为 truecurrentNum 变成 2长度 2contains(3)为 truecurrentNum 变成 3长度 3contains(4)为 truecurrentNum 变成 4长度 4contains(5)为 false断掉。长度 4。最长更新为 4。数字 3contains(2)为 true跳过。数字 2contains(1)为 true跳过。最后返回 4。看到没有只有 100、200、1 这三个起点真正执行了 while 循环其他数字全部在一次 contains 判断之后直接跳过。整个流程的耗时主要就是每个数字被查询常数次的开销。2.3 摊还分析为什么嵌套循环不是 O(n^2)很多人第一次看到这个解法都会觉得外层 for 循环里面套一个 while 循环这不是妥妥的 O(n^2) 吗这里要用摊还分析的视角来看。关键事实是while 循环只在当前数字是序列起点的时候才会执行而被 while 数过的那些数字在后续的外层遍历中一定不会再次进入 while。为什么因为 while 数过的数字一定都有num - 1在集合里它们在外层循环里都会被起点判断直接拦截。所以整个算法执行过程中所有元素被“向上连续查找”的次数加在一起不会超过 n 次。一句话解释每条连续序列只会被完整遍历一次所有序列的总长度加起来不可能超过数组里不同元素的总数 n。因此外层 O(n) 加上内层总共 O(n) 的消耗整体是 O(n)。空间上因为要存一个 HashSet是 O(n)。这就是哈希解法比排序解法高明的地方它把“查找某个数是否在数组里”从线性时间压到了常数时间又用“只枚举起点”把重复的遍历全部消掉了。两个手段缺一不可。3. Java 实现为什么选 HashSet 而不是 HashMap3.1 这题的查询只有“存不存在”Set 天然够用我第一次用哈希解法时第一版写的是MapInteger, Boolean map new HashMap()键存数字值存一个 true本质上拿 Map 当 Set 用。这种写法能跑通但很业余。原因很简单算法从头到尾只回答一个问题——“某个数字在不在集合里”这是一个纯粹的成员查询不需要任何键值映射。HashSet 在 Java 里底层就是 HashMap 的包装语义更精准代码读起来也更干净。用哈希表解决“存在性”问题时先想想自己到底需不需要 value。需要 value 才用 Map只需要判断存不存在就用 Set。这个选择不是性能上的巨大差异更多是代码表达的问题。面试官看到你用Map存一个用不到的 value第一印象就是你对自己的数据结构还不够熟练。3.2 遍历 Set 而不是遍历原数组能省掉重复元素带来的无效计算这是实际写代码时最容易忽略的细节。如果你写成for (int num : nums) { if (!numSet.contains(num - 1)) { // ... } }假设输入是[1, 1, 1, 2, 2, 2, 3]第一个 1 是起点从 1 数到 3得到长度 3第二个 1 又是起点又数一遍 1、2、3第三个 1 再来一遍。虽然因为取最大值最终结果还是 3不会出错但做了大量无用功。更极端的场景是数组里同一个数字重复几千次而它又是一条非常长序列的起点你就会白白重复几千次完整的 while 遍历虽然最终答案不受影响但性能明显下降。正确做法是遍历 Set 本身for (int num : numSet) { // ... }因为 Set 天然去重每个数字只处理一次。这个细节不影响正确答案但能让你的代码在“最坏情况下”依然保持稳定的 O(n) 表现。3.3 完整代码与边界条件逐个验证class Solution { public int longestConsecutive(int[] nums) { SetInteger numSet new HashSet(); for (int num : nums) { numSet.add(num); } int longestStreak 0; for (int num : numSet) { // 只有 num - 1 不存在时num 才是连续序列的起点 if (!numSet.contains(num - 1)) { int currentNum num; int currentStreak 1; while (numSet.contains(currentNum 1)) { currentNum 1; currentStreak 1; } longestStreak Math.max(longestStreak, currentStreak); } } return longestStreak; } }依次验证边界条件空数组[]Set 为空longestStreak 保持 0返回 0正确。单元素[5]Set 只有 55 的contains(4)为 false进入 while但contains(6)为 false长度 1返回 1正确。负数混合[-5, -4, -3, 0, 1]-5 是起点数到 -3 得到长度 30 是另一个起点数到 1 得到长度 2最长是 3正确。哈希集合对负数没有特殊处理只是普通的 contains 查询。数组里有Integer.MAX_VALUEcurrentNum 1会溢出成负数但contains查的是一个负数只要输入里没有这个负数循环就会停止。不会出现死循环也不会出现错误结果。这个细节一般遇不到但真被问起来至少知道它不会造成 bug。4. 容易翻车的几个细节以及我的验证思路4.1 重复元素会把排序解法带进沟里排序解法里重复元素是最容易翻车的点。比如数组[1, 1, 2, 3]如果没有处理重复遍历到第二个 1 时1 1不满足“差值 1”的条件按 else 分支重置 current导致结果出错。所以排序解法里必须写if (nums[i] nums[i - 1]) continue;这一行。但很多人第一次写的时候会漏掉这个判断或者只在脑子里想着“重复元素不影响最长长度”就跳过了结果一提交就错。哈希解法就没有这个问题。因为只要遍历 Set重复元素在源头就被去掉了不需要额外写去重逻辑。这是哈希解法的另一个隐性优势——它不是依赖你去“处理”重复而是从一开始就不存在重复。4.2 一个非常隐蔽的 1 错误还有一个小坑是我在本地手动测试时发现的。如果把 while 条件误写成while (numSet.contains(currentNum)) { currentNum; currentStreak; }这就出大事了。当 currentNum 是起点时contains(currentNum)一定为 true所以第一轮循环会把当前数字自己又算一遍然后 currentNum 加 1下一轮又查新值。最终统计出来的长度会比正确结果大 1。比如单元素[5]正确结果是 1但这段错误代码会输出 2。这个错误特别隐蔽因为普通用例下多 1 很难一眼看出来。我的习惯是写完哈希解法先跑一个单元素用例如果输出不是 1那基本就是这里出了问题。4.3 我常用的极端用例测试清单刷这种算法题我很少只跑题目给的示例就提交。以下是我会本地跑一遍的用例直接复制去测试就行输入数组期望最长连续长度设计目的[]0空数组边界[5]1单元素边界[1, 1, 1]1全重复元素[1, 2, 3, 4, 5]5一条完整长序列[100, 200, 300]1完全无连续关系[-1, 0, 1, 2, 3]5负数连续[0, 1, 2, 1, 2, 3]4重复元素混在序列里[Integer.MIN_VALUE, Integer.MAX_VALUE]1极端整数值这套用例覆盖了空数组、单元素、全重复、长连续、无连续、负数、极端值几类典型场景。跑完这些代码的正确性基本就有底了。4.4 关于“排序法也能过”的自我提醒我在写题解和跟人讨论时发现很多人会说“排序法提交也过了为什么非要用哈希”。这个想法在学生阶段很常见我也经历过。但从面试角度说题目给你一个复杂度要求本质上是在筛选你有没有复杂度意识。排序法在数据量小的时候和哈希法耗时差别不大可一旦数据量到百万级别O(n log n)和O(n)的差距就会非常明显。哈希解法不只是为了“通过”而是通过这道题练习一种思维方式看到存在性查询先想哈希看到重复遍历先想怎么剪枝。这才是 LeetCode 题目真正的练习价值。5. 面试官爱追问的变体提前想好不慌5.1 变体一不仅要长度还要输出具体的连续序列面试官如果觉得这个题你答得比较顺畅很可能会追加一句“能不能把最长的那条序列本身返回出来”。思路也很简单在原有代码基础上记录“最佳序列的起点”和“最佳序列的长度”。每当 currentStreak 超过 longestStreak 时更新bestStart num、bestLen currentStreak。最后遍历生成从 bestStart 到 bestStart bestLen - 1 的数组即可。if (currentStreak longestStreak) { bestStart num; bestLen currentStreak; }复杂度不变只是多记两个变量。这个变体考察的是你理不理解自己算法里的“信息流”——原本只关心最大值现在需要关心最大值对应的自变量区间你会发现代码改动非常小。5.2 变体二二维网格上的最长连续路径这是我在面试复盘里见过的一个延伸题。给定一个 m x n 的矩阵每个格子有一个整数要找一条上下左右相邻的路径路径上的值严格递增且每次加 1问最长路径长度。这题就不能直接用这一套哈希法了因为路径是受“位置邻居”约束的而不是只受“值是否存在”约束。但它的思想有相通之处同样要找到“起点”来避免重复计算。具体做法是记忆化 DFS。一个格子只有在其上下左右不存在“比它小 1 的格子”时才有可能作为路径起点从起点开始向值大 1 的邻居递归搜索并且用 memo 记录每个格子出发的最长路径长度。这样每个格子最多被计算一次整体复杂度 O(m x n)。这个变体和原题的关联点在于都是通过“找起点”来避免重复搜索。你如果能在面试里说出这层联系面试官会觉得你是真的理解了。5.3 变体三流式输入怎么维护最长连续序列还有一类变体是把输入改成数据流。假设每来一个新数字你都要快速回答当前已出现数字里的最长连续序列长度。这种情况下哈希解法要先把全集装进 Set 再统一遍历显然行不通。更合适的做法是并查集Union-Find每个新数字到来时分别看它的 num-1 和 num1 已经出现的数字把它们所在集合合并同时维护每个集合的大小。每次插入后更新全局最大集合大小即可。这个方案的空间和时间都和数据流规模相关而且能实时回答查询。我建议不用真的写出来但至少要能讲清楚思路并查集维护连通性、集合大小、合并时更新最大值。这样真被问起来你不会卡壳。这个题刷完之后我最大的感受是力扣 Hot 100 把它归到哈希类重点并不在“会用 HashSet”而在你如何想到“每个连续序列只从起点枚举一次”。这个避免重复计算的思想在二维路径、并查集、滑动窗口很多地方都能复用。Java 的 HashSet 只是把这种思想落地得最顺手的一个工具罢了。如果你现在也在刷这题建议别急着看答案先拿纸笔走一遍示例体会到“为什么中间节点被跳过”的那一刻你才算真正拿下这道题。