题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
进阶： 你可以设计并实现时间复杂度为 的解决方案吗？
示例 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
示例 3
输入：
nums = [1, 0, 1, 2]输出：
3解释： 即使数组中有重复数字，连续序列依然按照数值递增计算（如 0, 1, 2）。
提示
相关信息
-
标签： 数组 (Array)、哈希表 (Hash Table)、并查集 (Union Find)
-
难度： 中等 (Medium)
-
常见面试公司： Facebook, Google, Amazon, ByteDance
这个问题要求在 时间复杂度内找到未排序数组中最长的连续序列。解决这个问题的核心难点在于：如何在不排序（排序通常需要 ）的情况下，快速识别出哪些数字可以凑成连续的一串。
核心思路：哈希集合 (Set) 与“序列起点”判断
由于我们需要 的复杂度，这意味着我们最多只能对数组进行常数次的遍历。使用 哈希表（在 JS 中是 Set） 是最理想的选择，因为它能提供 的查找效率。
1. 为什么不能直接遍历？
如果我们对每个数字都向后查找是否存在 num + 1, num + 2... 那么对于像 [1, 2, 3, 4, 5] 这样的数组，我们在处理 1 的时候会查一遍，处理 2 的时候又会查一遍，导致效率退化到 。
2. 关键优化：只从“起点”开始计算
一个连续序列的起点有一个特征：它的前一个数字（num - 1）不在数组中。
-
如果
num - 1在数组中，说明当前的num只是某个序列的中间部分，我们直接跳过，不做重复计算。 -
如果
num - 1不在数组中，说明num是一个序列的开头。此时，我们才开始循环检查num + 1,num + 2... 直到序列断开。
这样保证了每个元素最多只会被访问两次（一次在 Set 中被检查，一次在作为某个序列的一部分被计数），从而达到 。
JavaScript 代码实现
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
if (nums.length === 0) return 0;
// 1. 将所有数字存入 Set，去除重复值并提供 O(1) 查找
const numSet = new Set(nums);
let longestStreak = 0;
// 2. 遍历 Set 中的每一个数字
for (const num of numSet) {
// 3. 判断当前数字是否是一个序列的“起点”
// 只有当 num - 1 不存在时，才说明 num 是起点
if (!numSet.has(num - 1)) {
let currentNum = num;
let currentStreak = 1;
// 4. 从起点开始，不断查找下一个连续数字
while (numSet.has(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
// 5. 更新全局最长长度
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
};
逻辑拆解与示例分析
以 nums = [100, 4, 200, 1, 3, 2] 为例：
-
放入 Set：得到
{100, 4, 200, 1, 3, 2}。 -
遍历到 100：
-
检查
99是否在 Set 中？不在。 -
100是起点。往后找101，不在。 -
当前长度
1，longestStreak = 1。
-
-
遍历到 4：
-
检查
3是否在 Set 中？在。 -
说明
4肯定不是起点（它属于以 1 或更小数字开头的序列），直接跳过。
-
-
遍历到 200：
-
检查
199不在。200是起点。往后找201不在。 -
longestStreak仍为1。
-
-
遍历到 1：
-
检查
0是否在 Set 中？不在。 -
1是起点！开启while循环：-
找到
2，长度变 2； -
找到
3，长度变 3； -
找到
4，长度变 4； -
找到
5？不在，循环结束。
-
-
更新
longestStreak = 4。
-
-
后续遍历（如 3, 2）：都会因为其前驱数字存在而直接跳过。
复杂度分析
-
时间复杂度：
-
建立
Set需要 。 -
虽然代码里有嵌套循环，但
if (!numSet.has(num - 1))确保了只有序列的第一个元素会触发内部的while循环。数组中的每个元素在整个过程中最多被处理两次。
-
-
空间复杂度：
- 我们需要一个
Set来存储所有的数字。
- 我们需要一个
为什么不用并查集 (Union-Find)？
虽然题目考点里提到了 union-find，但在 JavaScript 中，使用 Set 的解法通常更简洁且性能更优。并查集更适合处理动态合并的场景（比如不断有新数字加入），而本题是静态数组，哈希法是公认的最优解。