哈希集合+剪枝：O(n)破解最长连续序列的算法实战

刷题群里有同学吐槽，说LeetCode Hot 100里的「最长连续序列」是他见过的“最不讲武德”的题目之一。刚一看觉得很好做，排序后从头到尾数一遍就行了；然后瞄到题目要求，时间复杂度必须O(n)，人就愣住了。这道题属于典型的“思维题”——不考递归、不考动态规划、不考花哨的数据结构，就考你能不能把“连续”这个概念和哈希集合结合起来。我最早做这道题的时候也是排序一把梭，提交后看着性能排名哭笑不得。今天把完整思路、手写代码、面试追问和踩坑记录都整理出来，希望让卡在这道题上的朋友少走弯路。

1. 先看题目：三个隐藏的坑，每一个都能卡人

1.1 连续不是相邻，重复不能算多次

题目给的是一个未排序的整数数组，要求找出数字连续的最长序列的长度。很多人第一眼会把“连续”理解成“数组里相邻位置连续”，这是第一个误区。比如nums = [100, 4, 200, 1, 3, 2]，数字连续的最长序列是[1, 2, 3, 4]，长度是4。这些数字在数组里压根不是按顺序挨着的，甚至4和1之间还隔着一个200，但它们数值上是连续的。

第二个坑是重复元素。题目说的是“序列”，序列里的元素是从数组里选出来的，重复数字不能算多次。举个例子：[1, 2, 2, 2, 3]，1和3之间有2，但2出现了三次，连续序列仍然是1-2-3，长度是3，而不是5。你如果直接排序后遍历并统计连续递增的段数，遇到重复数字必须跳过，否则就会多算。很多初学者在本地测试单测用例能过，一提交发现结果偏大，多半就是忘了去重。

第三个坑写在题目末尾：时间复杂度要求O(n)。这个限制直接砍掉了一大批“正常人能想到的解法”。换句话说，这题考的不是你会不会写循环，而是你能不能设计出线性时间复杂度的算法。从面试角度看，这种限制本身就是提示——它暗示了某个数据结构能在O(1)时间内完成“判断某个数存在”的操作，那就是哈希表。

1.2 复杂度限制O(n)：排序法为什么直接出局

先看大家最容易想到的几条路线，以及它们各自死在哪儿。

最暴力的思路是：对每个数字，尝试从它开始不断加1，看加完之后的数是否在数组里。这个思路简单到什么程度呢？两层循环，外层遍历所有数字，内层从当前数字开始连续探测，最坏情况下数组是1到n的连续递增，每个数字都要往后探测n次，再加上每次探测都要扫描数组判断存在性，整体复杂度大概是O(n^3)。n稍微大一点就完全没法看。

排序法是个巨大的进步。先排序，再遍历一次，相邻数字如果差值为1就累加计数，否则重置。排序本身是O(n log n)，遍历是O(n)，总体O(n log n)。代码好写、思路直观，而且大多数时候能通过测试。但题目白纸黑字写了O(n)，排序法的复杂度就不满足要求。更麻烦的是，排序法对原数组做了修改（如果允许原地排序），有些面试官还会追问这一点。想靠排序法混过去，基本行不通。

排序法的教训其实很有价值：当你看到一个要求在O(n)时间内解决的问题，第一反应不该是“我要找更快的排序算法”，而是“我能不能不用排序就完成这个任务”。排序能做到的事，哈希集合往往也能做到，而且常常更快。

1.3 这道题在考什么：哈希表 + 剪枝思维

我把这题归类为“哈希表应用 + 剪枝思维”的典型题目。它不考动态规划、不考贪心、不考双指针，核心就一句话：能不能用一个哈希集合让“判断连续”这件事变得高效，同时通过剪枝避免重复计算。

这里的“剪枝”非常关键。最朴素的想法是：把所有数字放进哈希集合，然后对每个数字都往后数连续的长度，也就是每个数都当一次起点。这样做的复杂度是多少？最坏情况下，数组是[1, 2, 3, ..., n]，第一个数往后数n次，第二个数往后数n-1次，总次数是n + (n-1) + ... + 1，O(n^2)。虽然查找变成了O(1)，但重复计算仍然严重。

仔细想想：如果当前数字是3，而2在数组里存在，那么从3开始往后数的结果，一定是“从2开始往后数”的结果的子集。也就是说，3根本不是它所在连续序列的起点。真正需要从它开始统计的，只有那些“前一个数不存在”的数字。用代码表达就是if (!numSet.contains(num - 1))才进入计数逻辑，这就是剪枝。每个数字只会作为某个序列的起点被处理一次，整个内层循环的总工作量立刻降到了O(n)。

这个剪枝思路在各种算法题里都会出现，本质就是“识别出哪些计算是冗余的，然后跳过它”。面试的时候能把这点讲清楚，比机械地报出代码有价值得多。

2. 核心解法拆解：为什么哈希集合能写到O(n)

2.1 第一步：把所有数字装进HashSet

解法第一步是把数组中的全部数字放入一个哈希集合。这一步做了两件事：一是去重，重复数字只保留一份，避免后面统计长度时重复计数；二是把“判断某个数字是否存在”的时间复杂度降为平均O(1)。

在Java里用HashSet，在Python里直接用set()。这里要强调一个细节：往集合里放的是数字本身，而不是下标。刚才说过，连续序列是数值上的连续，和数组位置无关，所以数组下标在这个问题里没有任何用处。你要回答的只有一个问题：某个数字在不在集合里。HashSet.contains()和Python的in都是O(1)平均复杂度，这一步为整个算法提供了地基。

数据结构的选型可以做个简单对比：

装了HashSet之后，数组本来的顺序已经不重要了。你可以把它理解成把所有数字倒进一个盒子里，盒子里每个数字只有两种状态：有或者没有，连续不连续不取决于它们在盒子里的排列顺序。

2.2 第二步：从每段连续序列的起点开始数

核心逻辑可以拆成三个动作。

第一个动作是遍历集合中的每个数字。注意是遍历集合，不是遍历原数组。遍历集合的好处是天然去重，[1, 2, 2, 2, 3]这个数组放进集合后只剩1, 2, 3，你只需要处理这三个数。

第二个动作是判断当前数字是不是某段连续序列的起点。判断条件是num - 1是否存在。如果num - 1存在，说明当前数字不是所在连续序列的第一个数，从它开始统计是白费功夫，直接跳过。这个判断每次只花O(1)时间，但能把总计算量从O(n^2)降到O(n)。

第三个动作是，只有当num - 1不存在时，才从num开始，用while循环不断检查num + 1、num + 2……是否存在，同时累加长度。这个过程本质上是“顺着连续的值一路数下去”，直到某个数字不在集合里为止。数完一段后，用当前长度更新全局最长长度。

举个例子：集合里有{100, 4, 200, 1, 3, 2}。遍历到100时，99不存在，所以从100开始数，101不存在，长度1；遍历到4时，3存在，跳过；遍历到1时，0不存在，这是起点，从1数到2、3、4，得到长度4。这才是正确答案。

2.3 复杂度为什么是O(n)：均摊分析

这一步是面试时最容易讲不清楚的地方，也是这题真正的精髓。

外层循环遍历了整个集合，共n个元素，每个元素会做一次O(1)的contains判断，这部分是O(n)。

内层while循环表面上看结构复杂，但因为有了“只有起点才进入”的剪枝条件，每个数字至多在内层循环中作为“后继”被访问一次。换句话说，某一段连续序列[x, x+1, x+2, ..., y]，只有x会启动while循环，循环会依次访问x+1, x+2, ..., y，这些数字在其他任何起点启动的while循环里都不会再被访问。

把所有while循环访问的元素次数加起来，每个元素最多贡献一次，所以内层循环整体是O(n)。外层O(n)加内层O(n)，总复杂度O(n)。空间复杂度是O(n)，因为HashSet最坏情况下需要存n个数字。

理解这个均摊分析有一个生活化的类比：想象你有一抽屉袜子，要找最长的一段连续编号。如果你拿每只袜子都向后翻找，你会翻很多次；但如果只从“没有前一号的那只袜子”开始翻，每只袜子最多被你拿到手里一次，总操作次数就控制住了。

这里有个容易混淆的点要说清楚：contains操作平均是O(1)，但最坏情况下哈希冲突严重时会退化。不过在面试场景和LeetCode实际数据下，哈希表的O(1)是成立的，不用在复杂度分析里纠结最坏情况，面试官要听的就是均摊O(n)的结论。

3. 手写AC代码：从Java到Python的实现细节

3.1 Java版完整代码与逐行注释

先说Java版本，这是面试中最常用的语言之一，也方便对比其他解法。完整代码先贴出来：

class Solution { public int longestConsecutive(int[] nums) { Set<Integer> numSet = new HashSet<>(); // 第一步：把所有数字放入哈希集合，去重 for (int num : nums) { numSet.add(num); } int maxLen = 0; // 第二步：遍历集合，而不是遍历原数组 for (int num : numSet) { // 剪枝：如果num-1存在，说明num不是连续序列起点 if (!numSet.contains(num - 1)) { int cur = num; int curLen = 1; // 从起点向后数连续的数字 while (numSet.contains(cur + 1)) { cur += 1; curLen += 1; } maxLen = Math.max(maxLen, curLen); } } return maxLen; } }

有几个细节值得单独拎出来讲。

第一，外层遍历的是numSet而不是nums。如果遍历原数组，重复元素会导致同一个连续序列被反复统计。虽然剪枝条件下重复的数字也会因为num - 1存在而跳过，但如果数组里有大量重复值，遍历集合更清爽，逻辑更符合“集合里每个数字只处理一次”的语义。

第二，maxLen初始化为0。这覆盖了空数组的情况：集合是空的，外层循环一次不执行，返回0。如果数组只有一个元素，比如[5]，5的num - 1即4不存在，进入内层循环，4+1=6不存在，curLen为1，返回1。

第三，while (numSet.contains(cur + 1))里一定要记得在循环体内更新cur。有人图省事直接写while (numSet.contains(num + 1))，那会陷入死循环或永远数不出正确长度。

3.2 Python版几行搞定

Python的写法更加简洁，关键是代码量更少、可读性更好：

class Solution: def longestConsecutive(self, nums: List[int]) -> int: num_set = set(nums) max_len = 0 for num in num_set: if num - 1 not in num_set: cur = num cur_len = 1 while cur + 1 in num_set: cur += 1 cur_len += 1 max_len = max(max_len, cur_len) return max_len

注意Python写in操作时要养成用集合的习惯。如果你用的是list，num - 1 not in nums这一步就是O(n)，整体复杂度直接变成O(n^2)，这题就没法AC了。set的in才是O(1)。刷题时不注意这点特别容易翻车，本地小数据集看不出问题，提交后大数组直接超时。

还有一次性传入set(nums)和for num in num_set的写法，让“去重”和“遍历集合”合二为一，非常符合Python风格。不过有一点值得注意：set(nums)会创建新的集合对象，原数组保持不变。空间复杂度O(n)是绕不开的。

3.3 实现细节中的两个“小魔鬼”

第一个魔鬼是内层while循环的边界条件。假设集合里有{1, 2, 3, 4, 5}，从1开始，1的num - 1即0不存在，进入循环，cur从1逐渐变成5，curLen从1到5，6不在集合中，循环终止，maxLen更新为5。整个过程正确，没有数组越界问题。因为集合的contains方法是纯查询，不涉及下标访问，所以不存在“越界”这种说法，这也是哈希集合会比数组方便的地方。

第二个魔鬼是num - 1检查的方向。让我把这里说得细一点：有的题解会写if (!numSet.contains(num + 1))再从后往前数，即处理递减序列。这种写法也能AC，但理解成本和代码可读性都不如统一从起点向后数。关键是你要保持一致性：检查前一个数、从当前向后数，每一步逻辑要形成闭环。实际写的时候千万别混搭，比如检查num - 1却数num - 1, num - 2的递减，或者检查num + 1却从num向后加1，都会逻辑错乱。

我还想补充一个很多初学者会忽略的点：不要试图在统计过程中删除集合里的元素来“优化”。有些同学认为，既然已经统计过2、3、4了，就把它们从集合里删掉，外层循环能少几个元素。这在原理上是可行的，Java里用Iterator删除会有额外复杂度，Python里边遍历边修改集合直接报错。当前这个解法已经足够高效，没必要画蛇添足。

4. 实战踩坑实录：那些让代码从TLE到AC的教训

4.1 常见错误速查表

这题在LeetCode上的错误提交集中在超时和答案偏大两类。下面这张表我根据自己做题和解惑的经验整理过，非常实用：

最危险的是“答案正确但超时”这种情况，跑小数据集全过，一交大用例全是红色TLE。我第一次做这题就是这样，排序法在LeetCode上其实能通过不少测试用例，但就是卡在最后一个超大数据集上，这种失败最打击人。排查方法很简单：把输入数组换成[1, 2, 3, ..., n]这样的最坏情况，数一下内层循环总执行次数，立刻能看出问题。

4.2 面试官连续追问怎么答

面试中做完这道题，面试官大概率会追加一些问题。你得提前把答案准备好。

第一个高频追问是“为什么要用HashSet而不是HashMap”。回答要点：HashMap还需要关注键值对，这里只需要判断存在性，不需要存储额外信息，所以HashSet的语义更准确。实现层面HashSet底层就是HashMap，但面向的问题不同，用HashSet代码更简洁。

第二个追问是“空间复杂度能不能优化到O(1)”。这是一个比较有难度的追问。答案是可以尝试，但需要牺牲时间或者修改原数组。比如先排序再遍历，空间复杂度能到O(1)（原地排序），但时间复杂度变成O(n log n)。如果题目不强制O(n)时间，这是一个合理权衡。如果硬要同时满足O(n)时间和O(1)空间，在通用场景下没有简单解法，可以跟面试官讨论基数排序、位图等思路，但不要装懂，承认限制并说明取舍就好。

第三个追问是“重复元素怎么处理”。你只需要指出HashSet天然去重即可。面试官可能会继续问：如果换成List，你需要怎么改才能正确？这时候要说：要么排序后跳过重复值，要么用marked数组标记。核心是让每个数字只参与一次统计。

第四个追问更进阶：“如果你的内存装不下所有数字怎么办？”这是考察大数据处理的思路。可以先说外部排序配合分块处理，也可以提一下布隆过滤器做近似判断，但精度会有损失。在面试里遇到这种题，重点不是给出完美答案，而是展示你有“数据规模变了之后算法要随之调整”的敏感度。

4.3 容易混淆的题：最长连续序列和最长非降子序列

刷题热词里经常把“最长连续序列”和“最长非降子序列”放在一起，很多朋友会搞混。这里必须明确区分：最长连续序列要求的是数值上的连续，比如1、2、3、4，数字之间严格相差1，而且只关心数字是否在数组里出现过；最长非降子序列是动态规划领域的经典问题，要求的是“保持原数组相对顺序、可以不连续、非递减”的子序列。

打个比方：最长连续序列就像查一段连续的编号牌，少一个号都不行；最长非降子序列就像从一列队伍里挑几个人出来，他们的身高依次不降低，中间隔了谁无所谓。

这两个问题对应的数据结构也完全不同。最长连续序列用哈希集合，核心是存在性查询和剪枝；最长非降子序列用动态规划或者贪心+二分，核心是状态转移和子序列长度累加。如果你在LeetCode上搜Hot 100发现有道题叫“最长递增子序列”，别把这两题混为一谈。面试官如果故意把这两题放在一起问，八成是想考察你区分“连续性”和“有序性”的能力。

4.4 一道差不多的变体：加上“返回具体序列”怎么办

面试官在写完这道题后常会追加一个变体：不仅返回最长长度，还要返回这个连续序列本身。比如[100, 4, 200, 1, 3, 2]要输出[1, 2, 3, 4]。

这时候思路基本不变，只是在while循环里额外记录起始数字和长度，或者把访问到的数字收集进一个列表。具体做法：检测到num是起点后，从num开始，用一个临时列表依次添加current，直到current+1不存在。循环结束后，如果当前序列长度大于历史最长长度，就把临时列表拷贝出来。

这里有一个需要注意的坑：如果数组里存在多段相同长度的最长序列，题目没有明确规定时，可以默认返回第一段即可，但最好在注释里说明，或者在实现时选择编号最小的那段，避免面试官觉得你考虑不周。

5. 最后再分享一个小技巧：用边界值自测你的代码

题目写完之后，不要急着提交，先用几个边界用例自测一下。我的习惯是准备五组数据：

空数组[]，应当返回0。单元素数组[7]，应当返回1。全重复数组[2, 2, 2, 2]，应当返回1。负数混合数组[-3, -2, -1, 0, 1]，应当返回5。以及一段中间断开的数组[1, 3, 5, 7, 9]，应当返回1。

负数的情况尤其值得测，因为num - 1在负数上同样适用，没有特殊情况，但新手容易怀疑“负数和正数能不能连起来”。[-3, -2, -1, 0, 1]这个例子就很好地说明了：连续序列可以从负数开始，一直延伸到正数，哈希集合完全不关心正负号。

我后来做这道题，还发现一个心态层面的收获：第一遍用排序法AC过的人，多半不会觉得这题难；但真正理解了HashSet剪枝之后，才会发现自己之前压根没抓到题目核心。这个从“能过”到“理解为什么能过”的转变，是整个Hot 100刷题过程中最有价值的部分之一。希望你也能从这道题里体会到，一个简单的数据结构加上一个好的剪枝策略，能带来多大的性能提升。