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

很多刷题的人第一次见到 LeetCode 128“最长连续序列”这道题第一反应是排序排完序扫一遍不就完了嘛。要是你面试时真这么答面试官多半会追问一句“能不能做到 O(n)” 这道题之所以被列为经典中的经典恰恰是它的名字看起来简单——“最长连续序列”——但要求你从 O(n log n) 跳到 O(n)考察的是对哈希表底层能力和“连续序列怎么表示”的理解。我当年第一次手撕这道题也翻过车后来把这题的暴力解、排序解、哈希解和并查集思路全梳理了一遍才算彻底吃透。下面把我的完整笔记分享出来。1. 读懂题意这道题到底在问什么1.1 连续序列与子序列的边界先看题面给定一个未排序的整数数组 nums找出其中数字连续的最长序列的长度要求算法时间复杂度 O(n)。这里的“连续序列”指的是x, x1, x2, ...这样的形式而且元素在数组里出现即可不要求它们在原数组中的位置相邻。也就是说这是一个“值域上的连续性”问题而不是“下标上的连续子数组”问题。我见过不少初学者把这道题和“最长连续递增子序列”搞混。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然后不断查 x1、x2、x3……直到某个数不存在于数组中记录连续长度取最大值。但问题在于如果什么都不加限制每个数字都会被反复向上探测。例如数组是[1,2,3,4,5,6,100]从 1 开始能探测到 6从 2 开始又能探测到 6这样总复杂度会变成 O(n^2)。在 LeetCode 的测试数据下n10^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 不是起点跳过。遍历 20099 不存在起点长度 1。遍历 10 不存在起点探测 1、2、3、4、5……长度 4。遍历 32 存在跳过。遍历 21 存在跳过。最终答案 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(vectorint nums) { unordered_setint 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) { SetInteger 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)哈希集合存储全部元素。这在 n10^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先自己写暴力解哪怕超时也要理解为什么慢。再看排序解理解“排序去重扫描”的完整流程。最后改成哈希集合解确保能够独立讲清 O(n) 的论证。有余力的话用并查集再实现一遍加深对“集合合并”和“动态连通性”的理解。这样一轮下来你不仅刷了一道题还顺带复习了排序、哈希表、复杂度分析、并查集四个知识点。面试时如果遇到相关问题也能很快迁移。最后再分享一个小技巧手写这道题时很多人在while cur_num 1 in num_set这一步会把cur_num和原数组变量混用。我在白板上写的时候习惯把外层循环变量命名为num把探路变量命名为cur_num一眼就能看出谁是“起点候选”谁是“向前走的指针”。这个命名习惯帮我少踩了很多低级错误。希望这篇笔记也能让你的手撕过程更顺畅。