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, 1, 2, 3, 4, 5, 6, 7, 8]）

解题思考过程

第一步：理解问题

要找的是数值上连续的序列，不是数组下标上连续的子数组。比如数组 [100, 4, 200, 1, 3, 2]，连续序列是 1, 2, 3, 4，它们在数组中不相邻，但数值上连续。

第二步：暴力解法（排序后遍历）

最直接的思路：排序，然后遍历数组数连续段。

nums.sort() → [1, 2, 3, 4, 100, 200]
然后遍历：遇到 nums[i] == nums[i-1]+1 就计数+1，否则重置。

时间复杂度：O(n log n) - 排序
空间复杂度：O(1) 或 O(n)

思路简单，但不满足题目 O(n) 时间要求。

第三步：哈希表查邻居

能不能不排序，直接判断某个数的前后是否存在？用哈希 Set：

对每个数 v：

• 如果 v-1 在 Set 中 → 说明有比它小 1 的数，v 不是起点，跳过。
• 如果 v-1 不在 Set 中 → v 可能是起点，尝试往后扩：v, v+1, v+2, ... 看最远能到多少。

这样，每个连续段只会从它的起点开始数一遍，中间的元素不会重复统计。

第四步：为什么整体是 O(n)

看起来有 for + while 两层循环，但实际上每个元素最多只被访问两次：

1. 外层 for 循环时被访问一次。
2. 作为某个起点序列中的一员，在 while 循环中被访问一次。

而且"不是起点"的元素（存在 v-1）不会进入 while。所以整体就是 O(n) 级别的访问总量，不会退化到 O(n²)。

第五步：举例验证

以 nums = [100, 4, 200, 1, 3, 2] 为例：

Set = {100, 4, 200, 1, 3, 2}

v=100: 100-1=99 不在 Set → 起点
  扩 101? 不在。长度 1。ans=1

v=4:   4-1=3 在 Set → 不是起点，跳过

v=200: 199 不在 Set → 起点
  扩 201? 不在。长度 1。ans=max(1,1)=1

v=1:   0 不在 Set → 起点
  扩 2? 在。3? 在。4? 在。5? 不在。长度 4。ans=max(1,4)=4

v=3:   2 在 Set → 不是起点，跳过

v=2:   1 在 Set → 不是起点，跳过

最终 ans = 4，正确。

当前解法：哈希 Set 起点枚举

注意：原代码 while 循环里缺少 cur++，会导致死循环。以下是修正后的版本。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  // 开辟一个 Set 来保存数组的值，我们遍历 Set 来判定连续，
  // 并且满足 O(n)，因为只会从起点开始，不会多次遍历
  const s = new Set();
  for (let i = 0; i < nums.length; i++) {
    s.add(nums[i]);
  }

  let ans = 0;
  for (const v of s) {
    if (!s.has(v - 1)) {
      let cur = v;
      let m = 1;
      while (s.has(cur + 1)) {
        cur++;     // 修正：别忘了 cur 自增，否则死循环
        m++;
      }
      ans = Math.max(m, ans);
    }
  }

  return ans;
};

代码逐行解释

建 Set

const s = new Set();
for (let i = 0; i < nums.length; i++) {
  s.add(nums[i]);
}

把数组放进 Set，主要两个目的：

1. 去重 — 数组里重复的元素对连续序列长度没贡献（例：[0,0,1]，连续长度还是 2）。用 Set 自动去重。
2. O(1) 查询 — s.has(x) 可以 O(1) 判断某个数是否存在，是整个方案 O(n) 时间的基础。

也可以简写成 const s = new Set(nums)，效果一样。

答案初始化

let ans = 0;

最长长度的计数器。空数组时循环不执行，直接返回 0，无需额外处理边界。

枚举起点

for (const v of s) {
  if (!s.has(v - 1)) {

遍历 Set 中每个值 v：

• 关键判断：!s.has(v - 1)。即 v-1 不存在，说明比 v 小 1 的数没出现过，v 就是连续序列的起点。
• 如果 v-1 存在 → v 不可能是起点，直接跳过，不去 while 循环，避免重复统计。

这一步是整个算法 O(n) 的关键——每个连续序列只从最小的数（起点）开始扩一次。

从起点向后扩

    let cur = v;
    let m = 1;
    while (s.has(cur + 1)) {
      cur++;
      m++;
    }

从起点 v 开始，不断看 cur+1 是否在 Set 中：

• cur 标记当前连续段走到哪个数。
• m 记录当前连续序列长度，初始值 1（至少起点自己算一个）。
• 每找到 cur+1，就把 cur 前进一位、长度 m +1。
• cur++ 非常关键：如果漏掉（像原代码那样），cur 永远停在 v，cur+1 永远是 v+1，while 条件永远为真 → 死循环。

更新答案

    ans = Math.max(m, ans);

把当前起点对应序列的长度和 ans 比较，保留最大值。

返回结果

return ans;

执行过程示例

以 nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] 为例：

Set = {0, 3, 7, 2, 5, 8, 4, 6, 1}（自动去重去掉了第二个 0）

v=0: 0-1=-1 不在 Set → 起点
  cur=0, m=1
  cur+1=1? 在 → cur=1, m=2
  cur+1=2? 在 → cur=2, m=3
  cur+1=3? 在 → cur=3, m=4
  cur+1=4? 在 → cur=4, m=5
  cur+1=5? 在 → cur=5, m=6
  cur+1=6? 在 → cur=6, m=7
  cur+1=7? 在 → cur=7, m=8
  cur+1=8? 在 → cur=8, m=9
  cur+1=9? 不在。结束 while
  ans = max(0, 9) = 9

v=3: 2 在 Set → 不是起点，跳过
v=7: 6 在 Set → 不是起点，跳过
v=2: 1 在 Set → 不是起点，跳过
v=5: 4 在 Set → 不是起点，跳过
v=8: 7 在 Set → 不是起点，跳过
v=4: 3 在 Set → 不是起点，跳过
v=6: 5 在 Set → 不是起点，跳过
v=1: 0 在 Set → 不是起点，跳过

返回 9，正确！

可以看到：除了起点 0 真正进入 while 扩了 8 次，其他 8 个元素都只在 if 判断里 O(1) 过了一下就跳过——总计访问量远小于 n²。

复杂度分析

• 时间复杂度：O(n)。

  • 建 Set：O(n)。
  • 外层 for：每个元素一次，O(n)。
  • 内层 while：总和最多 O(n)（每个元素最多被 while 访问一次）。
  • 合计 O(n)。

• 空间复杂度：O(n)。Set 最多保存数组中所有不同的元素。

为什么这个算法不是 O(n²)

很多人看到 "for + while" 就以为是 O(n²)，但它有个关键性质：

每个连续段只会从起点进入一次 while，段内其他元素直接跳过 for。

所以 while 循环执行的总次数，最多等于 Set 中元素的个数（每个元素最多只被 while 扩到一次）。这和朴素的"对每个数都 while 扩一遍"完全不同。

替代解法：排序

思路直观但时间不达标，作参考：

var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0;
  nums.sort((a, b) => a - b);
  let ans = 1;
  let m = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) continue;       // 去重
    if (nums[i] === nums[i - 1] + 1) {
      m++;
    } else {
      m = 1;
    }
    ans = Math.max(m, ans);
  }
  return ans;
};

• 时间复杂度：O(n log n)
• 空间复杂度：取决于排序实现

两种解法对比

解法	时间复杂度	空间复杂度	特点
哈希 Set 起点枚举	O(n)	O(n)	最优时间，空间换时间，面试首选
排序	O(n log n)	取决于实现	思路直观，时间不达标

易错点

1. while 里忘写 cur++：while (s.has(cur+1)) 的循环体必须 cur++，否则只要 v+1 在 Set 中就是死循环。原代码就有这个问题，修正后加了 cur++。

2. 用数组而不是 Set 查询：如果把 s.has() 换成数组的 includes()，查询是 O(n)，整体时间会退化成 O(n²)。必须用哈希结构（Set 或 Map）保证 O(1) 查询。

3. 起点判断写反：应该是"不存在 v-1"才进入起点（!s.has(v-1)）。如果写成 s.has(v-1)，会变成只从中间或结尾进入，结果完全不对。

4. 忘记去重：题目数组可以有重复值（如 [0,0,1]）。不建 Set 直接遍历原数组，会导致同一个数被多次当成起点。Set 天然去重。