0128.最长连续序列
难度：🟡 中等
标签：数组、哈希表、并查集
链接：128. 最长连续序列
题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 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
解题思路
核心思想
本题要求以 O(n) 的时间复杂度找出最长的连续序列。这排除了需要 O(n log n) 的排序算法。核心思想是利用哈希数据结构实现快速查找，从而避免不必要的重复计算。
思路选择
哈希集合（Set）法 是解决此问题的标准最优思路。
我们可以先将所有数组元素存入一个哈希集合
Set中。这有两个好处：一是自动去重，二是提供了 O(1) 的平均时间复杂度来查找一个元素是否存在。然后，我们遍历这个哈希集合。对于集合中的每一个数
num，我们判断它是否是一个连续序列的起点。一个数num是起点的充要条件是num - 1不在集合中。如果
num是一个起点，我们就从这个数开始，不断地检查num + 1,num + 2, ... 是否存在于集合中，以此来计算当前连续序列的长度，并更新全局的最大长度。
关键步骤
处理边界情况：如果数组为空，直接返回 0。
初始化集合：创建一个哈希集合
numSet，并将nums的所有元素存入。初始化最大长度：
maxLength = 0。遍历集合：遍历
numSet中的每一个数字num。寻找序列起点：对于每个
num，检查numSet中是否存在num - 1。如果存在，说明num不是序列的起点，直接跳过。计算序列长度：如果
num - 1不存在，说明我们找到了一个序列的起点。从这个点开始，通过一个while循环不断检查num + 1,num + 2, ... 是否存在于numSet中，并记录下当前序列的长度currentLength。更新最大值：用
currentLength更新maxLength。返回结果：遍历结束后，
maxLength就是最长连续序列的长度。
代码实现
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
if (nums.length === 0) {
return 0;
}
const numSet = new Set(nums);
let maxLength = 0;
for (const num of numSet) {
// 只有当 num-1 不存在时，才把 num 当作序列的起点，避免重复计算
if (!numSet.has(num - 1)) {
let currentNum = num;
let currentLength = 1;
// 从起点开始，计算当前连续序列的长度
while (numSet.has(currentNum + 1)) {
currentNum++;
currentLength++;
}
// 更新最大长度
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
};
复杂度分析
时间复杂度：O(n) 其中 n 是数组
nums的长度。虽然代码中有嵌套循环，但while循环的每次执行都对应numSet中一个未被内部循环访问过的元素。因此，每个元素最多被访问两次（一次在for循环，一次在while循环），总时间复杂度是线性的。空间复杂度：O(n) 我们需要一个哈希集合来存储所有不重复的元素，在最坏的情况下（所有元素都不同），空间消耗与 n 成正比。
相关题目
总结
本题是哈希表应用的经典案例。通过将问题转化为“寻找序列的起点”，并利用哈希表 O(1) 的查找特性，巧妙地将时间复杂度控制在线性级别，避免了排序带来的额外开销。