最长连续序列问题详解：哈希集合实现O(n)时间复杂度的算法

最长连续序列这道题是很多人在刷题生涯里绕不开的一道经典题。简单来说就是在给定一个未排序的整数数组时找出其中数字连续的最长序列的长度。比如数组[100, 4, 200, 1, 3, 2]最长连续序列是[1, 2, 3, 4]长度就是 4。这道题看起来简单但要求时间复杂度达到 O(n) 时传统排序方案就失效了需要用哈希集合来优化查找。这篇文章从思路拆解、代码实现到边界处理做一个完整的复盘适合准备算法面试的开发者、系统学习数据结构的朋友参考。1. 整体思路拆解为什么排序不是这道题的最优解1.1 先从暴力解法说起最容易想到的方案是先排序再遍历。排序之后连续的整数一定会出现在相邻位置遍历一次就能统计出最长序列长度。代码也就十几行逻辑非常直观。但我必须要说这道题如果直接用排序解法面试中大概率只能拿基础分。原因在于排序的时间复杂度是 O(n log n)当 n 达到百万级别时排序开销会非常可观。排序解法虽然不满足性能要求但它的思路是很好的参考连续序列天然和“相邻”这个概念有关。如果我们能想办法让“判断某个数的下一个数是否存在”这个操作变成 O(1)就能用线性时间完成任务。正是这个想法把思路引向了哈希集合。1.2 哈希集合为什么是首选工具要判断一个数是否存在于数组中如果直接遍历数组每次查找都是 O(n)整体就会退化到 O(n²)。这个复杂度在几万个元素时还能接受到了百万级别就难以运行了。哈希表的核心价值在于查找时间复杂度接近 O(1)。将数组所有元素放入哈希集合后续判断某个数是否存在只需要一次哈希查找即可。这个特性直接满足了 O(n) 的要求。从工程角度看编程语言内置的哈希集合都有很好的实现比如 Java 的 HashSet、Python 的 set、C 的 unordered_set它们内部通过哈希函数将元素映射到桶中平均情况下查找开销是常数级。使用哈希集合还有一个额外好处天然去重。数组[1, 2, 2, 3]中数字 2 重复出现如果不做去重连续序列统计时可能被计数两次产生错误的长度。哈希集合会自动去掉重复元素这一点在实际编码时非常省心。1.3 算法流程的核心逻辑哈希集合解法的大致流程可以概括为遍历数组将所有元素放入哈希集合。再次遍历数组对于每个数字判断它是否是一个连续序列的起点。如果num - 1不在集合中说明num就是某个序列的起点从num开始不断递增检查num 1、num 2…… 是否在集合中统计长度。如果num - 1在集合中说明num是中间元素跳过。这里最核心的一点是“起点判断”。假设数组是[1, 2, 3, 4]遍历到 2 时因为 1 已经存在于集合中说明 2 不是起点直接跳过。只有遍历到 1 时才会开始一次完整的序列统计。这样做的意义是每个元素最多被访问两次一次外层遍历一次作为起点后的内层遍历总复杂度仍是 O(n)而不是 O(n²)。这一点是整道题的精髓。2. 核心细节解析与实操要点2.1 为什么“起点判断”能保证线性复杂度很多人第一次接触这道题时会有疑问如果每个元素都需要向后不断遍历那不就成了嵌套循环吗为什么复杂度还是 O(n)关键在于嵌套循环的执行次数不是 n² 次而是受哈希集合中的连续区间长度支配。当一个数字不是起点时直接跳过不会触发内层循环当一个数字是起点时内层循环会一直走完整个连续区间但这个区间里的其他元素再次出现时都会被起点判断挡住不会重复走一遍。举一个形象点的例子数组[100, 4, 200, 1, 3, 2]起点分别是 100、200、1内层循环分别走了 1、1、4 步总共只走了 6 步恰好等于元素个数。无论数据怎么组合每个元素最多只会在一次内层循环中被访问到这也是时间复杂度能被控制在 O(n) 的根本原因。2.2 复杂度分析时间复杂度遍历数组两次第一次建立集合是 O(n)第二次每个元素要么被跳过要么作为起点触发一次内层循环所有内层步数总和也是 O(n)所以整体是 O(n)。空间复杂度哈希集合存储了数组中的所有元素因此是 O(n)。如果数组本身可以原地修改空间上也没办法降到 O(1)因为哈希集合是必须要有的数据结构。从实际运行的视角看这里有一个容易被忽略的细节集合中元素的数量等于去重后数组的长度对于大量重复的数据空间占用会小于原始数组这算是一个额外的正向收益。2.3 边界条件与常见陷阱我在实际写题过程中总结出几个比较容易翻车的点空数组如果nums为空最长连续序列长度应该是 0。代码里要提前处理或者让初始答案longest 0自然就能覆盖这种情况。单元素数组长度为 1 的数组答案是 1。循环逻辑自然能处理但要注意初始值不能设置成负数否则答案会比实际小。重复元素[1, 2, 2, 3]这种场景如果不用哈希集合做去重而是遍历数组逐个判断很容易把 2 统计两次。用哈希集合后就完全不担心。负数和跨度大的正数例如[-1, 0, 1]或者[100, 101, 102]连续序列的定义同样适用于负数判断逻辑不受数值符号影响。有些没经验的实现会用数组下标来标记是否出现遇到负数或者远超数组长度的数字就会出问题而哈希集合则天然规避了这个限制。这些边界条件在面试中经常被当作考察点。面试官通常不会满足于“代码能跑”而是会追问空数组、重复元素、负数这些情况能不能正确处理。把边界条件整理清楚比急着写出跑通样例更加重要。2.4 哈希集合底层实现与选择注意点虽然哈希集合在这道题中表现出色但它的底层实现仍然有值得关注的地方。不同语言对哈希集合的实现各不相同Python 的set基于哈希表Java 的HashSet内部基于HashMapC 的unordered_set底层是哈希表。其中 C 的unordered_set在某些实现下遇到大量哈希冲突时最坏情况会退化成线性查找导致整体复杂度退化为 O(n²)。不过这种极端情况通常只在数据被恶意构造时出现竞赛和实践中很少遇到。如果要进一步极端优化可以考虑使用布尔数组加偏移量的方式模拟哈希但这样需要提前知道数值范围并且会引入额外的空间开销。在大多数实际场景下内置哈希集合已经足够。3. 实操过程与代码实现细节3.1 完整代码实现Python / Java / C先给一份最常用的 Python 实现代码简洁直观def longestConsecutive(nums): num_set set(nums) longest 0 for num in num_set: if num - 1 not in num_set: current_num num current_len 1 while current_num 1 in num_set: current_num 1 current_len 1 longest max(longest, current_len) return longest这里的重点在于外层遍历的是num_set而不是nums。如果遍历nums在含有重复元素时同一个起点会被重复处理效率会下降。虽然答案仍然正确但时间开销会超出 O(n) 的预期。遍历集合则能保证每个数字只处理一次。Java 版本的思路完全一致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 currentNum num; int currentLen 1; while (numSet.contains(currentNum 1)) { currentNum; currentLen; } longest Math.max(longest, currentLen); } } return longest; }C 版本用unordered_set代码结构大同小异int longestConsecutive(vectorint nums) { unordered_setint numSet(nums.begin(), nums.end()); int longest 0; for (int num : numSet) { if (!numSet.count(num - 1)) { int currentNum num; int currentLen 1; while (numSet.count(currentNum 1)) { currentNum; currentLen; } longest max(longest, currentLen); } } return longest; }三个版本的逻辑完全一致建立集合、遍历集合、基于起点判断触发内层计数。不同之处只在于语法细节。3.2 逐行解释代码中的关键操作我把 Python 版本的代码拆开来看一下每一行的含义。num_set set(nums)这行将数组转成集合底层会遍历数组一次时间复杂度 O(n)同时完成去重。longest 0初始化最终答案为 0这样可以正确应对空数组场景。for num in num_set遍历集合的每一个元素。这里要特别强调外层遍历集合而不是原始数组因为集合已经去重能防止重复数字导致的重复计数。if num - 1 not in num_set是整个算法的灵魂判断。这个条件决定了当前数字是否为一个连续序列的起点。如果存在num - 1说明前面还有更小的数字那么num只是序列中的某个后继元素如果从它开始统计会产生重复工作反之num就是一个区间的起点进入内层循环。内层while循环从起点开始不断检查current_num 1是否在集合里每存在一个就自增计数。由于哈希查找是常数时间整个while循环的时间消耗正比于连续区间的长度。longest max(longest, current_len)更新全局最优解。这一步在每次找到一个完整连续区间后执行确保最终返回的是所有区间长度的最大值。3.3 测试用例设计为了验证代码的健壮性可以准备一组测试用例输入数组预期结果说明[100, 4, 200, 1, 3, 2]4经典场景多个零散序列[]0空数组边界[1]1单元素数组[1, 2, 0, 1]3包含重复元素去重后序列为[0, 1, 2][-3, -2, -1, 0, 1]5连续负数与正数混合[9, 1, 8, 2, 7, 3, 6, 4, 5]9完整的一个连续区间[10]1只有一个元素本身就是最长连续序列把这些用例跑一遍能覆盖绝大多数边界条件确认代码没有明显的逻辑缺陷。3.4 拓展输出最长连续序列本身有些面试官会进一步追问不只是返回最长连续序列的长度而是把序列本身输出出来。这个需求只需要在统计过程中记录起始值和结束值最后统一构造答案即可。def longest_consecutive_sequence(nums): num_set set(nums) best_start None best_end None best_len 0 for num in num_set: if num - 1 not in num_set: current_num num current_len 1 while current_num 1 in num_set: current_num 1 current_len 1 if current_len best_len: best_len current_len best_start num best_end current_num return list(range(best_start, best_end 1)) if best_start is not None else []这个版本在最坏情况下需要额外 O(n) 空间来存储返回的列表时间复杂度和原版一致。实际业务中如果需要把连续区间作为后续流程的输入这个扩展版本更有实用价值。4. 常见问题与排查技巧实录4.1 高频问题排查速查表我把实践中遇到的高频卡点整理成了表格方便对照排查。问题现象可能原因解决方案运行结果偏小外层循环遍历了原始数组而不是集合重复元素导致统计被打断改为遍历集合运行结果偏大把起点判断条件写反确认if num - 1 not in num_set空数组报错没有处理空数组初始值设置错误确保longest初始值为 0超时数据规模大且没有起点判断每个元素都触发内层循环确认加入了起点判断结果包含重复数字没有使用集合去重直接在原数组上双重循环先用集合存储所有元素4.2 从理论到工程连续序列在真实场景的应用这道题虽然表面上是面试算法题但在真实工程中同样有广泛的运用场景。用户连续登录天数统计给定一组用户登录日期需要找出最长连续登录天数本质就是求日期数组中的最长连续序列长度。股价连续上涨区间分析股票数据中连续上涨的交易日数量用于判断走势强度。资源连续可用时间段系统中一段资源存在多条可用记录需要合并连续时间段并找到最大连续区间。断点检测日志数据中连续递增的序号如果断掉说明可能丢失了记录需要找出最长连续区间来定位异常。在业务中处理日期序列时需要注意一个细节日期本身不是整数直接判断“1 天”是否存在时需要将日期转换为时间戳或者标准日期格式。这个问题用哈希集合时也容易踩坑比如日期字符串格式不一致、时区问题等。我的建议是先用统一的规范化格式清洗数据再进入算法流程不然排序都无法解决问题。4.3 独家避坑技巧我在实际调试过程中积累了几个很有价值的经验分享出来。第一个技巧是外层遍历优先使用集合而不是原始数组。如果是数组重复元素会导致同一个起点被多次触发虽然最终答案正确但效率会下降。面试中如果要追求极致的复杂度分析就应该意识到这一点。第二个技巧是如果题目要求返回最长连续序列本身而不是长度方向不要搞错。有些人在内层循环里把各个区间拼接最后再取最大但容易出现区间顺序交错的问题。我建议记录起点和终点最后统一构造答案序列这样逻辑清晰且不容易出错。第三个技巧是使用 Cunordered_set时要慎防哈希扩容带来的性能抖动。极端情况下如果数据量非常庞大性能可能达不到预期。工程上可以通过提前reserve预留容量unordered_setint numSet; numSet.reserve(nums.size() * 2);这样能减少哈希扩容次数在数据量大的场景下会有可感知的性能提升。第四个技巧是注意“连续”的定义。如果要统计的是最长连续递增序列严格递增且间隔为 1上述算法依然适用。但如果间隔是固定的比如每 2 天一次就需要在while循环里加个步长参数。实际场景里“连续”二字的概念可能被放大为“间隔固定”。4.4 与同类算法的对比最后做一个对比看看最长连续序列与几个类似问题的差异。算法问题核心数据结构时间复杂度区别点最长连续序列哈希集合O(n)寻找数字连续的最长区间最长递增子序列二分查找 动态规划O(n log n)不要求连续可以跳过元素最长连续非递减子序列双指针 / 贪心O(n)关注数组顺序不强调数值区间连续性这三个问题看起来相似但解法完全不同。最长连续序列的关键在于“存在性判断”与数组中元素原本顺序无关最长递增子序列则强调保持原顺序因此必须依赖动态规划或二分优化。如果你正准备面试我的建议是把这道题实现三遍。第一遍看完文章思路后自己独立写出代码第二遍尝试用不同语言实现第三遍把“输出最长连续序列本身”的变体也写一遍。这道题虽然短小但它考察的是对哈希结构特性与线性复杂度分析的理解做透之后对很多其他题目的解题能力也会有连带提升。我在实际调试中还发现一个有趣的现象很多人一上来就想着怎么排序却忽略了题目已经明确要求线性复杂度。这其实反映出一种思维惯性——看到数组就想到排序。用哈希集合去重并对元素做存在性检查是一种典型的“空间换时间”策略在很多其他问题中也能复用比如判断两个数组交集、检测环是否存在等。希望这篇文章能让你在遇到“连续”“存在”“去重”这些关键词时自然联想到哈希集合这个工具。