企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文基于《算法通关手册》中的 0128. 最长连续序列题解，系统讲解「在未排序数组中找出数字连续的最长序列长度」这一经典哈希表考题。你将掌握哈希集合去重 +「只从序列起点向外延伸」的 O(n) 线性解法、复杂度推导，并了解该题标签中的并查集（Union Find）视角如何与哈希解法殊途同归。本题同时被收录于本仓库的面试 100 题列表与面试 200 题列表，属于算法面试的必刷高频题。

1. 题目概述

1.1 题目大意

给定一个未排序的整数数组nums，要求找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度，并且要求使用时间复杂度为 $O(n)$ 的算法解决此问题。

这里的「连续序列」指的是数值上相邻（差值为 1）的一组整数，与元素在数组中的物理位置无关。例如数组[100, 4, 200, 1, 3, 2]中，数字[1, 2, 3, 4]数值上连续，尽管它们在原数组中分散在不同位置。

1.2 数据范围与示例

数据约束（题目明确规定）：

• $0 \le nums.length \le 10^5$
• $-10^9 \le nums[i] \le 10^9$

示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

示例 2 中数组含重复元素0，去重后连续序列为[0, 1, 2, 3, 4, 5, 6, 7, 8]，长度为 9。这个示例很好地提示了：必须先去重，重复元素不影响序列长度，却会干扰遍历计数。

值得注意的是，同样的题目还以 LCR 119. 最长连续序列 的形式出现在剑指 Offer（LCR 系列）题解中，两道题的核心思路与代码完全一致，可互相参考。

2. 暴力做法的两种思路与瓶颈

在引入 O(n) 解法之前，先明确暴力做法的局限性，才能理解哈希表优化的价值。

2.1 思路 A：先排序，再扫描

对数组排序后，连续的数字会聚集在一起，只需一趟线性扫描统计相邻差值恰好为 1 的最长段即可。

• 排序本身的时间复杂度下限是 $O(n \log_2 n)$（可参考仓库中关于排序算法分类与复杂度的说明，快速排序、归并排序等高级排序算法均为 $O(n \log n)$）。
• 排序后扫描的复杂度为 $O(n)$，但整体仍受限于排序的 $O(n \log n)$。

因此排序做法不满足题目 O(n) 的硬性要求。

2.2 思路 B：枚举每个数作为起点，向后暴力匹配

枚举数组中的每个数num，以其为起点，不断尝试匹配num + 1、num + 2、…… 是否存在。最坏情况下，每个起点都需要向后匹配len(nums)次，总时间复杂度为 $O(n^2)$。

当n接近 $10^5$ 上限时，$O(n^2)$ 显然不可接受。

3. 思路 1：哈希表（集合）优化解法

3.1 核心优化点

暴力思路 B 之所以慢，是因为它对每一个元素都尝试向外延伸，而这些元素中的大多数其实处于某个序列的「中间」或「末尾」，从它们出发会重复计算大量前缀。

哈希表解法的关键洞察只有两点：

1. 用集合去重：Python 的set底层是哈希表，元素的插入与成员查询均为 $O(1)$ 平均时间复杂度（哈希表的基本原理可参考仓库中的哈希表专题文档，其中详细介绍了哈希函数设计与哈希冲突解决策略）。
2. 只从序列起点开始延伸：一个数num是「某段连续序列的起点」，当且仅当num - 1不在集合中。只有满足这个条件的元素才值得向内层while循环延伸，从而保证每个序列的每个元素至多被访问一次。

3.2 算法步骤

1. 将数组存入集合nums_set进行去重；用curr_streak维护当前连续序列长度，用ans维护最长连续序列长度。
2. 遍历集合中的每个元素num：
   • 若num - 1在集合中，说明num不是序列起点，直接跳过（这是整个算法的效率关键）；
   • 若num - 1不在集合中，说明num是某段序列的起点，则从num开始，依次判断num + 1、num + 2、…… 是否在集合中，并同步累加curr_streak；
3. 每次内层延伸结束后，用ans = max(ans, curr_streak)更新全局最长长度。
4. 遍历结束后返回ans。

3.3 完整代码

以下代码严格对应原题解，可直接运行：

class Solution: def longestConsecutive(self, nums: List[int]) -> int: ans = 0 nums_set = set(nums) for num in nums_set: if num - 1 not in nums_set: curr_num = num curr_streak = 1 while curr_num + 1 in nums_set: curr_num += 1 curr_streak += 1 ans = max(ans, curr_streak) return ans

代码逐行解读：

• set(nums)：一次遍历完成去重，同时将原始数组的重复元素剔除，避免后续重复统计（对应示例 2 中的两个0）；
• if num - 1 not in nums_set：序列起点的判定条件，是 $O(1)$ 复杂度的来源；
• while curr_num + 1 in nums_set：利用哈希表 $O(1)$ 查询能力，逐格向外延伸当前序列；
• ans = max(ans, curr_streak)：内层循环结束后，用当前序列长度刷新全局答案。

3.4 正确性验证

以示例 1 的nums = [100,4,200,1,3,2]手动推演：

• 集合为{1, 2, 3, 4, 100, 200}；
• 遍历到1：0 not in set，起点成立，延伸2 → 3 → 4，curr_streak = 4，ans = 4；
• 遍历到2：1 in set，跳过；
• 遍历到3、4：前驱均在集合中，跳过；
• 遍历到100：99 not in set，起点成立，100 + 1 = 101不在集合，curr_streak = 1，ans保持 4；
• 遍历到200：同理，curr_streak = 1；
• 最终返回4。✅

3.5 复杂度分析

• 时间复杂度：$O(n)$。
  • 将数组存入集合进行去重：$O(n)$；
  • 集合成员查询x in set：$O(1)$（平均情况，哈希表特性）；
  • 遍历集合时，所有「非起点」元素只被检查一次前驱后即跳过；所有「起点」元素引发的内层while延伸，总步数不超过 $n$（因为每段连续序列只会从其起点被完整遍历一次，序列之间互不重叠）。
  • 综上，整体为 $O(n)$，满足题目约束。
• 空间复杂度：$O(n)$。需要额外的哈希集合存储所有不重复元素，最坏情况下（数组元素全部不同）集合大小等于数组长度。

3.6 注意事项

• 遍历的是nums_set（集合）而不是原始nums，可避免重复元素导致的重复起点判断；
• 集合大小写敏感、数值范围可达 $\pm 10^9$，因此不能使用计数数组/布尔数组模拟集合（空间不可行），这正是必须使用哈希表的原因——哈希表只存储实际出现过的元素，与数值范围无关。

4. 思路 2：并查集（Union Find）视角

题目标签中同时标注了「并查集」，说明该题存在基于并查集的建模方式。虽然哈希解法更简洁，但理解并查集版本有助于打通「连通性」思维，并可复用仓库中的并查集专题文档与其基础实现源码。

4.1 建模思想

将每个数字看作一个节点，数值上相邻的两个数（差值为 1）之间建立一条「连续边」。那么：

• 一个连续序列 ⇔ 一张连通分量；
• 最长连续序列的长度 ⇔ 节点数最多的那个连通分量的大小。

具体步骤可设计为：

1. 使用哈希表建立「数值 → 下标」的映射，把可能很大的数值域压缩到 $[0, n)$ 的索引空间（因为 $-10^9 \le nums[i] \le 10^9$，直接以数值建数组不可行）；
2. 初始化并查集，每个元素自成一个集合；
3. 遍历每个元素x，若x + 1存在于映射表中，则执行union(x, x+1)；
4. 统计每个连通分量的节点个数，取最大值。

4.2 与仓库并查集实现对应

仓库中的并查集基础实现提供了三个核心接口，可直接套用于上述流程：

• find(x)：查找元素根节点（路径压缩版self.fa[x] = self.fa[self.fa[x]]为隔代压缩）；
• union(x, y)：合并两个集合，返回是否发生合并；
• is_connected(x, y)：判断两元素是否同属一个集合。

需要额外补充的是：统计连通分量大小时，需要在union成功后维护size数组（按大小合并的并查集变体，可参考仓库中的 tree_unionFind_UnoinBySize.py），每合并一次就将两集合大小相加，最后取最大size即可。

4.3 两种思路的对比

面试中优先推荐哈希表解法，代码短、易解释、无额外类定义负担；并查集解法适合在考察「连通性建模」的场合展示，或作为复习并查集原理的载体。

5. 易混淆题型辨析：连续 vs 递增 vs 子序列

本仓库题解体系中存在多道名称相近的题目，理解差异可避免面试中张冠李戴：

• 0128. 最长连续序列（本题）：要求数值连续（差值恰为 1），元素可无序，O(n) 哈希解法；
• LCR 119. 最长连续序列：与本题完全同构的 LCR 版本，解法相同；
• 0300. 最长递增子序列：要求严格递增（差值至少为 1，且保持原数组相对顺序），属于单串线性动态规划问题，时间复杂度为 $O(n \log n)$ 或 $O(n^2)$，详见线性 DP 专题中的练习题目列表。

一句话总结：本题的「连续」只看数值邻居关系、不看原数组顺序，因此集合（哈希表）天然适配；而「子序列」类问题必须保留顺序约束，需借助 DP 状态设计。

6. 在《算法通关手册》中的定位与延伸学习

本题被《算法通关手册》收录于多个关键位置：

• 面试 100 题列表 与面试 200 题列表：标注为「并查集、数组、哈希表 / 中等」；
• 题解总列表 与题目分类列表：可在哈希表分类下找到本题及其姊妹题。

围绕本题的核心知识点，仓库提供了成体系的配套资料：

1. 哈希表原理：哈希表专题系统讲解哈希函数（直接定址法、除留余数法、平方取中法、基数转换法等）与哈希冲突解决（开放地址法、链地址法），是理解本题set查询 $O(1)$ 的底层依据；
2. 并查集原理与实现：并查集专题 讲解快速查询（基于数组）与快速合并（基于森林）两种实现，配合 tree_unionFind.py、tree_unionFind_QuickUnion.py 等源码可深入理解find/union的实现细节与路径压缩优化。

总结

本题的核心考点可浓缩为三点：

1. 识别 O(n) 约束：排序法 $O(n \log n)$、暴力枚举法 $O(n^2)$ 均不合格，必须借助哈希表；
2. 只从序列起点延伸：通过num - 1 not in set判起点，保证每个元素至多访问一次，是 O(n) 成立的充分条件；
3. 理解去重的必要性：重复元素不影响答案，却会破坏计数，集合天然解决此问题。

掌握哈希表解法后，可进一步用并查集视角重新审视本题，并借助仓库中的哈希表、并查集专题文档巩固底层原理，为后续处理「连通分量」「区间合并」类问题打下基础。

• 教程
• 文档
• 知识库