LeetCode128：哈希集合巧解最长连续序列
一、题目回顾
LeetCode 128 题「最长连续序列」是一道中等难度的数组题，核心要求如下：给定一个未排序的整数数组 nums，找出其中数字连续的最长序列（不要求序列元素在原数组中连续）的长度，且必须设计时间复杂度为 O (n) 的算法。
示例直观理解：
- 输入
nums = [100,4,200,1,3,2]，输出4（最长序列是[1,2,3,4]）； - 输入
nums = [0,3,7,2,5,8,4,6,0,1]，输出9（完整连续序列0-8）。
二、解法思路：哈希集合 + 起点判定
题目要求 O (n) 时间，因此不能用排序（排序时间 O (nlogn)），需要借助「哈希集合」的快速查找特性（查找操作 O (1)）。
核心思路是：
- 将数组元素存入哈希集合，实现 “是否存在某数” 的快速判断；
- 遍历集合中的每个数
x，仅当x-1不在集合中时，才将x作为 “连续序列的起点”； - 从起点
x开始，依次查找x+1、x+2...是否在集合中，统计该序列的长度； - 维护一个全局变量，记录所有序列的最长长度。
这个思路的巧妙之处在于：非起点的数会被跳过，每个数只会被遍历一次，从而保证整体时间复杂度为 O (n)。
三、C++ 代码解析
先看完整代码，再逐行拆解：
cpp
运行
class Solution { public: int longestConsecutive(vector<int>& nums) { // 1. 将数组元素存入哈希集合（去重+快速查找） unordered_set<int> hash(nums.begin(), nums.end()); int len = 0; // 记录最长序列长度 // 2. 遍历集合中的每个数 for (int x : hash) { // 3. 仅当x-1不存在时，x才是序列起点（避免重复计算） if (hash.count(x - 1)) { continue; } // 4. 从起点x开始，扩展连续序列 int y = x + 1; while (hash.count(y)) { ++y; } // 5. 更新最长长度（y-x是当前序列的长度） len = max(len, y - x); } return len; } }; 代码关键细节
- 哈希集合的作用：
- 用
unordered_set存储数组元素，既实现了去重（重复元素不影响连续序列长度），又能在 O (1) 时间内判断某数是否存在。
- 用
- 起点判定逻辑：
if (hash.count(x - 1)) continue;：如果x-1存在，说明x不是当前连续序列的起点（比如 x=2 时，若 x-1=1 存在，则 2 属于以 1 为起点的序列），直接跳过，避免重复遍历。
- 序列长度计算：
- 从起点
x出发，用y不断向后扩展（y++），直到y不在集合中，此时y - x就是当前连续序列的长度。
- 从起点
四、复杂度分析
- 时间复杂度：O(n)
- 存入集合的时间是 O (n)；
- 遍历集合时，每个元素最多被访问 1 次（只有起点会触发后续的扩展循环，非起点会被跳过），因此整体遍历时间是 O (n)。
- 空间复杂度：O(n)
- 哈希集合存储了数组的所有元素，空间开销与数组长度成正比。
五、解法小结
这个解法的核心是通过 “起点判定” 避免重复计算，结合哈希集合的快速查找，既满足了 O (n) 的时间要求，又保证了逻辑的简洁性。
相比暴力解法（枚举每个数后遍历后续元素，时间 O (n²)），这个方法用空间换时间，是这道题的最优解之一。
