LeetCode 128最长连续序列：从排序到O(n)哈希表全解析

很多刷题的人第一次见到 LeetCode 128“最长连续序列”这道题，第一反应是排序：排完序扫一遍不就完了嘛。要是你面试时真这么答，面试官多半会追问一句：“能不能做到 O(n)？” 这道题之所以被列为经典中的经典，恰恰是它的名字看起来简单——“最长连续序列”——但要求你从 O(n log n) 跳到 O(n)，考察的是对哈希表底层能力和“连续序列怎么表示”的理解。我当年第一次手撕这道题也翻过车，后来把这题的暴力解、排序解、哈希解和并查集思路全梳理了一遍，才算彻底吃透。下面把我的完整笔记分享出来。

1. 读懂题意：这道题到底在问什么

1.1 连续序列与子序列的边界

先看题面：给定一个未排序的整数数组 nums，找出其中数字连续的最长序列的长度，要求算法时间复杂度 O(n)。

这里的“连续序列”指的是x, x+1, x+2, ...这样的形式，而且元素在数组里出现即可，不要求它们在原数组中的位置相邻。也就是说，这是一个“值域上的连续性”问题，而不是“下标上的连续子数组”问题。

我见过不少初学者把这道题和“最长连续递增子序列”搞混。LeetCode 128 不要求在原数组中有先后顺序，比如数组是[100, 4, 200, 1, 3, 2]，答案是 4，因为 1、2、3、4 这四个数字虽然在原数组里分散开，但它们本身是连续整数，就能拼成一个长度为 4 的连续序列。理解了这一点，你才知道为什么排序解法可行：因为排序把值域归位了，连续性自然就暴露出来了。

1.2 示例拆解

拿官方的例子来说：

• 输入[100, 4, 200, 1, 3, 2]
• 输出4
• 解释：最长数字连续序列是[1, 2, 3, 4]，长度为 4。

为什么不是 100 和 200？因为它们前后都没有紧挨着的值，所以单独每个序列长度都是 1。这里也透露了一个重要信息：一组连续数字的贡献只取决于它能连多长，而不取决于单个数的大小。

再来一个容易出错的例子：[0, 3, 7, 2, 5, 8, 4, 6, 0, 1]，这里有两个 0，答案是 9。因为0,1,2,3,4,5,6,7,8全在数组里，多余的那个 0 不会让它更长，也不会让序列断开。重复元素在计算时要跳过。

1.3 隐藏条件分析

题目里几个隐藏条件会直接影响算法选择：

• 数组未排序，长度最大可达 10^5，至少是 10^4 级别，O(n^2) 必然不可行。
• 元素范围是 32 位有符号整数，也就是说有负数，不能拿数组开桶直接映射。
• 时间复杂度要求 O(n)，等于把“排序再扫描”的常规思路堵死了一半。虽然面试时可以提排序解作为过渡，但最终一定要给出线性解。

另外注意，题目问的是“长度”，不是“序列本身”。很多变种题会要求输出最长连续序列的具体元素，那个只需要在计算过程中记录起点和终点即可，核心思路不变。

2. 先别急着写哈希：暴力解和排序解为什么不够

2.1 暴力枚举的复杂度

暴力思路很容易想到：枚举每一个数字 x，然后不断查 x+1、x+2、x+3……直到某个数不存在于数组中，记录连续长度，取最大值。

但问题在于，如果什么都不加限制，每个数字都会被反复向上探测。例如数组是[1,2,3,4,5,6,100]，从 1 开始能探测到 6，从 2 开始又能探测到 6，这样总复杂度会变成 O(n^2)。在 LeetCode 的测试数据下，n=10^5 时 O(n^2) 基本跑不动。

有人会想到用哈希表把数组存起来，这样“判断某个数是否存在”的耗时降到 O(1)，但枚举依然可能重复。暴力枚举的耗时瓶颈不在于单次查找，而在于重复起点太多。所以暴力解只能作为思路铺垫，不能作为最终答案。

2.2 排序解法与去重问题

排序解是最接近直觉的解法：先排序，然后扫描相邻元素。如果nums[i] == nums[i-1] + 1，当前连续长度 +1；如果相等，说明有重复元素，跳过；否则重置当前长度为 1。

这里有一个容易忽略的点：必须去掉重复值的影响。比如数组[1,2,2,3]，如果不过滤重复，扫描时会看到 2 和 2 相等，既不是 +1 也不是断层，代码如果没处理好就会错误地把长度算成 2。正确做法是遇到相等的元素直接跳过，不重置也不累加。

排序解的代码逻辑确实简单：

def longestConsecutive(nums): if not nums: return 0 nums.sort() ans = 1 cur = 1 for i in range(1, len(nums)): if nums[i] == nums[i - 1]: continue elif nums[i] == nums[i - 1] + 1: cur += 1 else: cur = 1 ans = max(ans, cur) return ans

这段代码在工程上是可用的，在面试时也能作为“最直观思路”来展示，但它的问题同样明显：排序本身是 O(n log n)，不满足题目的 O(n) 要求。

2.3 排序解的时间复杂度陷阱

你可能会想，sort之后扫描是 O(n)，整体不就是 O(n log n) 吗？面试官问的是“能不能 O(n)”，你答 O(n log n) 就是没达到要求。有的面试官比较宽松，允许先说排序解再优化；有的会直接要求“请用 O(n) 实现”。所以排序解可以作为热身，但不能停留在那一步。

还有个细节：nums.sort()在不同语言里实现不同，Python 的 Timsort 对基本有序数组表现接近 O(n)，但复杂度最坏仍是 O(n log n)，而且这道题的数组是未排序的，不能赌输入规模。你需要把注意力放在真正的 O(n) 算法上。

3. 关键优化：O(n) 哈希集合算法的本质

3.1 为什么要判断前驱节点

标准的 O(n) 解法利用哈希集合去重，然后只从“连续序列的起点”开始向后扩展。核心优化就一句话：如果 x-1 存在于集合中，说明 x 不是某个连续序列的起点，直接跳过，不从这个数开始探测。

为什么这样能保证 O(n)？原因很简单：每一个数字最多只会被访问两次。第一次是在外层循环中被取出；第二次是作为某个起点后的“后继节点”被内层循环探测到。而且只有一个元素是序列起点时，内层才会运行；一旦一个序列被探测完，序列中所有元素都不会再触发内层循环。

举个例子，数组[100, 4, 200, 1, 3, 2]：

• 遍历 100：判断 99 不存在，说明 100 是起点，探测 100、101、102……直到没有，长度为 1。
• 遍历 4：判断 3 存在，说明 4 不是起点，跳过。
• 遍历 200：99 不存在，起点，长度 1。
• 遍历 1：0 不存在，起点，探测 1、2、3、4、5……长度 4。
• 遍历 3：2 存在，跳过。
• 遍历 2：1 存在，跳过。

最终答案 4。

3.2 核心代码与逐行解读

Python 版本最简洁：

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

几个容易写错的地方：

• for num in num_set而不是for num in nums。虽然两者对结果影响不大，但用集合遍历可以天然跳过重复元素，从语义上更符合“每个数字只处理一次”的直觉。
• 判断条件必须是num - 1 not in num_set，不是num + 1 not in num_set。如果判断后继，会从所有中间节点开始重复探测，退化回 O(n^2)。
• while cur_num + 1 in num_set用cur_num临时变量递增，不要直接修改循环里的num，否则外层遍历会乱。

C++ 版本：

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> numSet(nums.begin(), nums.end()); int longest = 0; for (int num : numSet) { if (!numSet.count(num - 1)) { int curNum = num; int curLen = 1; while (numSet.count(curNum + 1)) { curNum++; curLen++; } longest = max(longest, curLen); } } return longest; } };

Java 版本：

class Solution { public int longestConsecutive(int[] nums) { Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } int longest = 0; for (int num : numSet) { if (!numSet.contains(num - 1)) { int curNum = num; int curLen = 1; while (numSet.contains(curNum + 1)) { curNum++; curLen++; } longest = Math.max(longest, curLen); } } return longest; } }

3.3 哈希方法的复杂度论证

时间复杂度：外层循环遍历 n 个元素，每个元素只检查num - 1是否存在，O(1)。内层 while 循环只在序列起点触发，而一个序列一旦被完整遍历，序列中的所有元素都不可能再作为其他序列的“内部节点”进入 while。因此内层循环总次数等于所有序列长度之和，不超过 n。

空间复杂度 O(n)：哈希集合存储全部元素。这在 n=10^5 时非常安全，实际内存占用大约为每个整数一个哈希桶，Python 的 set 会稍大一些，但通常不会成为瓶颈。

这样论证之后，面试官基本就满意了。我建议你在面试时把这个复杂度论证讲清楚，比干巴巴背代码有说服力得多。

4. 手撕面试中的边界条件与易错点

4.1 空数组

空数组[]应该返回 0。如果代码里把longest初始化为 0，自然没问题；但如果你习惯把最长长度初始化为 1，空数组就会出错。建议所有刷题都养成“先判空”或“初始化变量为 0”的好习惯。

4.2 重复元素

[1, 2, 2, 3]的答案应该是 3，而不是 2。用哈希集合后，重复的 2 会在numSet里只保留一个，遍历集合时不会因为重复元素导致错误累加。如果你用的是排序解法，必须显式跳过nums[i] == nums[i-1]的情况。

还有更隐蔽的情况：[0,0]答案 1。集合中只有一个 0，外层遍历一次，内层探测 1 不存在，返回 1。排序法要注意：跳过重复后，cur 不重置，需要额外处理。

4.3 负数与超大整数

数组里可能有负数，比如[-3, -2, -1, 0, 1]，答案 5。哈希集合处理负数没有任何问题，因为判断的是num - 1和num + 1是否在集合中，不涉及数组下标。C++ 的int要小心curNum + 1溢出，题目数据范围在 32 位有符号整数内，但极端情况如INT_MAX时curNum + 1会溢出。实际 LeetCode 测试数据通常不会给这种极端值，但严谨起见可以写成long long curNum或判断边界。

4.4 时间复杂度与语速平衡

很多人在面试时一上来就写哈希解，写完了面试官问“为什么是 O(n)”却讲不清。我的建议是：

• 先说排序解，让面试官看到你的基础思维。
• 接着指出排序不满足 O(n)，从而引出哈希集合思路。
• 边说边写，解释关键判断num - 1 not in num_set的原因。
• 最后把复杂度论证作为总结。

这套节奏大约 10 分钟就能完成。如果面试官只想要答案，直接写哈希解也完全可以，但在注释里或者口述里一样要说明“只从起点向后扩展”的设计动机。

5. 进阶扩展：从最长连续序列到并查集思路

5.1 并查集如何建模

除了哈希集合，这道题还有另一种经典做法：并查集。把连续相邻的值合并到同一个集合中，最后统计每个集合的大小，取最大值。具体做法是：遍历数组，将num与num + 1合并（如果num + 1存在）；合并时维护集合大小，最后返回最大 size。

下面是并查集思路的 Python 示例：

class DSU: def __init__(self, nums): self.parent = {x: x for x in nums} self.size = {x: 1 for x in nums} def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, a, b): if b not in self.parent: return ra, rb = self.find(a), self.find(b) if ra == rb: return if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] class Solution: def longestConsecutive(self, nums): if not nums: return 0 dsu = DSU(nums) for x in nums: if x + 1 in dsu.parent: dsu.union(x, x + 1) return max(dsu.size.values())

并查集在这道题里的意义更多是“练习数据结构建模”，面试手撕时能用哈希集合就用哈希集合，因为它更直观、代码更短。但理解并查集还有一个好处：处理“动态插入元素并实时维护最长连续序列长度”的变种题时，并查集往往比每插入一次就重建哈希集合更高效。

5.2 什么时候该用并查集

如果题目要求支持动态添加数字，并随时返回当前最长连续序列长度，哈希集合的静态扫描就需要维护一个“实时更新”的结构。这时可以用并查集，每次插入时尝试和左右邻居合并，O(α(n)) 几乎常数复杂度，就能维护全局最大 size。这种变体在面试里出现频率不高，但我确实见过。

5.3 变种题思路

LeetCode 128 的常见变形包括：

• 输出具体的连续序列：在哈希解中记录序列起点和终点即可。
• 求最长连续 1 的个数：那是另一个问题，不要混淆。
• 二维网格中的最长连续路径：核心思路是 DFS 记忆化搜索，不再使用哈希集合。
• 求最长非降子序列（非连续）：那就是 LIS，动态规划，和本题完全不同。

把这些变形放在一起对比，你会发现“连续”这个词在不同题里含义差别很大。LeetCode 128 的“连续”是值域上的连续，而 LIS 的“连续”是指序号递增但不要求数值相邻。做题时多问自己一句“这个连续是位置的连续还是值的连续”，能避免很多错误。

6. 我的踩坑记录与总结建议

6.1 第一次手撕翻车现场

我第一次做这道题时，写的是暴力枚举，加了一个set之后洋洋得意，觉得复杂度已经 O(n)。结果一提交，超时。原因是我的外层循环遍历nums，内层却从每个num开始无条件向上探测，遇到[1, 2, 3, ..., 50000]这种数据，从 1 到 49999 每个数都会向上走完一轮，复杂度直接 O(n^2)。

后来看到题解里的“只找起点”优化，才意识到问题出在“没有排除非起点元素”。这个坑我记了很久：暴力枚举和哈希解之间，差的不是数据结构，而是剪枝逻辑。

6.2 复盘笔记

那次翻车后，我给这道题写了一份复盘笔记：

• 连续序列的本质是“一段值域连续的数”，不是“一段下标连续的子数组”。
• 哈希集合能 O(1) 判断某个数是否存在，这正是题目 O(n) 的关键基础设施。
• 只从序列起点开始探测，是避免重复计算的唯一方法。
• 判断起点的方式是检查num - 1是否在集合中。
• 如果有重复元素，集合天然去重，无需额外处理。

现在刷手撕题，我最喜欢用这道题当“面试热身题”。它不涉及复杂的数据结构，但足够考察候选人的思维能否从“排序后扫描”跳到“哈希集合剪枝”。很多算法题其实都是这样：解法不难，难的是你能不能意识到前一个解法的瓶颈在哪。

6.3 建议刷题顺序

如果你正在准备算法面试，我的建议是这样练习 LeetCode 128：

1. 先自己写暴力解，哪怕超时，也要理解为什么慢。
2. 再看排序解，理解“排序+去重+扫描”的完整流程。
3. 最后改成哈希集合解，确保能够独立讲清 O(n) 的论证。
4. 有余力的话，用并查集再实现一遍，加深对“集合合并”和“动态连通性”的理解。

这样一轮下来，你不仅刷了一道题，还顺带复习了排序、哈希表、复杂度分析、并查集四个知识点。面试时如果遇到相关问题，也能很快迁移。

最后再分享一个小技巧：手写这道题时，很多人在while cur_num + 1 in num_set这一步会把cur_num和原数组变量混用。我在白板上写的时候，习惯把外层循环变量命名为num，把探路变量命名为cur_num，一眼就能看出谁是“起点候选”，谁是“向前走的指针”。这个命名习惯帮我少踩了很多低级错误。希望这篇笔记也能让你的手撕过程更顺畅。