128. 最长连续序列

题目描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列长度。

连续序列中的元素不要求在原数组中连续，只要求数值连续。要求设计并实现时间复杂度为 O(n) 的算法。

示例：

输入：nums = [100, 4, 200, 1, 3, 2]
输出：4
解释：最长连续序列是 [1, 2, 3, 4]，长度为 4。
输入：nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
输出：9
解释：最长连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]。

1. 题型判断

如果先排序，再扫描相邻数字，可以在 O(n log n) 时间内解决问题，但不满足题目要求的 O(n)。

要在线性时间内判断某个相邻数字是否存在，需要使用哈希集合：

Set.has(value) 的平均时间复杂度为 O(1)

先把数组中的数字全部放入 Set，之后就可以快速判断 num - 1 或 num + 1 是否存在。

但仅仅使用哈希集合还不够。如果从每个数字开始不断查找后继，例如从 1 查到 10000、再从 2 查到 10000，仍然可能退化成 O(n²)。

真正的关键是：只从一段连续序列的起点开始向右扩展。

2. 如何判断连续序列的起点

如果集合中不存在 num - 1，那么 num 前面没有连续数字，它一定是一段连续序列的起点：

if (!numberSet.has(num - 1)) {
  // num 是连续序列的起点
}

反过来，如果 num - 1 存在，说明 num 位于某段序列的中间或末尾。这段序列会在遍历到更小的起点时被完整统计，因此当前直接跳过：

if (numberSet.has(num - 1)) {
  continue;
}

例如集合为：

{1, 2, 3, 4, 100, 200}
  • 1 的前驱 0 不存在，所以从 1 开始扩展到 4。
  • 2、3、4 都存在前驱，不再重复扩展。
  • 100 和 200 的前驱不存在，各自形成长度为 1 的序列。

3. 算法步骤

  1. 使用 Set 保存数组中的所有数字，同时自动去除重复值。
  2. 遍历集合中的每个数字 num。
  3. 如果 num - 1 存在，说明它不是序列起点，直接跳过。
  4. 如果 num - 1 不存在，从 num 开始不断检查 num + 1、num + 2 等后继数字。
  5. 统计当前连续序列的长度，并更新全局最大值。

4. 代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  const numberSet = new Set(nums);
  let maxLength = 0;

  // 必须遍历去重后的 Set，不能遍历 nums：如果 nums 中有大量重复的序列起点，
  // 同一段连续序列会被重复向后扫描，最坏会退化为 O(n²) 并导致超时。
  for (const num of numberSet) {
    // 只从连续序列的起点开始扩展。
    if (numberSet.has(num - 1)) {
      continue;
    }

    let current = num;
    let currentLength = 1;

    while (numberSet.has(current + 1)) {
      current++;
      currentLength++;
    }

    maxLength = Math.max(maxLength, currentLength);
  }

  return maxLength;
};

currentLength 应在每次发现新起点时重新初始化为 1，这样它只表示当前这段序列的长度，不需要在循环末尾手动清零。

5. 示例推演

以：

nums = [100, 4, 200, 1, 3, 2]

为例，集合为：

{100, 4, 200, 1, 3, 2}
当前数字num - 1 是否存在处理方式当前序列最大长度
100否从 100 扩展[100]1
4是，存在 3跳过-1
200否从 200 扩展[200]1
1否从 1 扩展[1, 2, 3, 4]4
3是，存在 2跳过-4
2是，存在 1跳过-4

最终返回 4。

Set 的遍历顺序不影响结果。无论先访问哪个数字，只有序列起点会触发完整扩展。

6. 为什么时间复杂度是 O(n)

代码中存在 for 循环嵌套 while 循环，看起来可能是 O(n²)，但需要计算每个元素实际参与扩展的次数。

  • 创建哈希集合需要 O(n) 平均时间。
  • 外层循环最多访问 n 个不同数字。
  • 只有连续序列的起点会进入扩展循环。
  • 每个数字只会在所属序列从起点扩展时被访问一次，不会再从序列中间重复向后扫描。

假设所有数字被分成若干互不相交的连续序列，长度分别为：

L1, L2, ..., Lk

所有 while 循环的总执行次数与下式同阶：

L1 + L2 + ... + Lk <= n

因此平均时间复杂度为：

O(n) + O(n) = O(n)

更严谨地说，该结论依赖 JavaScript Set 插入和查询操作平均为 O(1)；在极端哈希冲突模型下不保证最坏 O(n)，但算法题通常按哈希表平均复杂度分析。

7. 正确性说明

每一段连续序列都会被统计

任意有限连续序列都有唯一的最小元素 start。由于 start - 1 不在集合中，算法遍历到 start 时一定会识别它为起点，并通过不断检查后继访问整段序列。

每一段连续序列只会被完整统计一次

序列中除起点之外的每个元素 x 都存在前驱 x - 1，所以它们不会触发扩展。只有唯一的起点会完整扫描该序列。

得到的一定是最长长度

算法统计了集合中的每一段极大连续序列，并用 maxLength 保存其中的最大长度，所以最终结果就是最长连续序列的长度。

8. 重复元素为什么不影响结果

题目关心数字是否存在，而不是某个数字出现了多少次。例如：

[1, 2, 2, 3]

最长连续序列仍然是 [1, 2, 3]，长度为 3，第二个 2 不应增加长度。

使用：

new Set(nums)

会自动去除重复数字，使每个数在连续序列中只计算一次，也避免外层循环重复处理相同值。

9. 边界条件与易错点

边界条件：

  • 空数组对应空集合，循环不会执行，返回初始值 0。
  • 只有一个数字时，该数字是起点，返回 1。
  • 所有数字都相同时，去重后只有一个数字，返回 1。
  • 负数同样适用，例如 [-2, -1, 0, 1] 的结果为 4。
  • 数组原有顺序不影响结果。

易错点：

  • 不要先排序，排序的时间复杂度为 O(n log n)，不满足题目要求。
  • 必须判断 num - 1 是否存在，而不是只从每个数字无条件向后扩展。
  • 连续指的是数值相差 1，不是元素在原数组中的下标连续。
  • 重复数字不能重复计入序列长度，应遍历去重后的集合。
  • 当前长度应从 1 开始，因为起点本身已经属于序列。
  • 更新答案应发生在当前序列扩展完成之后。

10. 常见错误方案

从每个数字开始向后查找

for (const num of numberSet) {
  let current = num;
  while (numberSet.has(current + 1)) {
    current++;
  }
}

对于 [1, 2, 3, ..., n]，它会分别从 1、2、3 等位置重复扫描后缀，总查询次数约为：

n + (n - 1) + ... + 1

时间复杂度退化为 O(n²)。

用数组下标充当哈希表

数字可能为负数，数值范围也可能远大于数组长度。创建一个从最小值到最大值的布尔数组，空间复杂度取决于数值跨度而不是元素数量，可能浪费大量空间。

把重复值计入长度

连续序列要求相邻数值依次加 1。重复出现的相同数字不会延长序列，必须先去重或在扫描时显式跳过。

11. 另一种线性解法：扫描后删除

还可以在找到任意数字后同时向左右扩展，并把访问过的数字从集合中删除：

var longestConsecutive = function (nums) {
  const numberSet = new Set(nums);
  let maxLength = 0;

  while (numberSet.size > 0) {
    const start = numberSet.values().next().value;
    numberSet.delete(start);

    let length = 1;
    let left = start - 1;
    let right = start + 1;

    while (numberSet.delete(left)) {
      left--;
      length++;
    }

    while (numberSet.delete(right)) {
      right++;
      length++;
    }

    maxLength = Math.max(maxLength, length);
  }

  return maxLength;
};

每个数字被成功删除一次，因此平均时间复杂度也是 O(n)。不过“只从起点扩展”的主解法更简洁，也更容易证明。

12. 复杂度分析

  • 时间复杂度：平均 O(n)。创建和遍历集合为线性时间，每个不同数字最多参与一次有效的序列扩展。
  • 空间复杂度：O(n)。哈希集合最多保存 n 个不同数字。

13. 面试追问

为什么不用并查集？

可以把每个数字看成节点，并合并数值相邻的节点。配合哈希表和按大小合并，并查集也能达到接近 O(n) 的时间复杂度，但实现和额外状态更多。本题只需序列长度，哈希集合从起点扩展更直接。

如果需要返回最长连续序列本身怎么办？

在更新最大长度时，同时记录当前序列的起点：

if (currentLength > maxLength) {
  maxLength = currentLength;
  bestStart = num;
}

最后生成从 bestStart 到 bestStart + maxLength - 1 的序列即可。如果存在多个最长序列，需要根据题目补充的规则决定返回哪一个。

为什么不能用滑动窗口？

滑动窗口通常依赖原数组中一段连续下标区间，而本题忽略原数组顺序，只关心数值集合中的连续关系。哈希集合更符合问题结构。

14. 可迁移总结

本题的核心思路可以概括为：

哈希集合提供 O(1) 平均存在性查询
  -> 通过“前驱不存在”识别唯一序列起点
    -> 每段连续区间只扩展一次
      -> 总扫描次数保持线性

当题目要求在线性时间内处理无序数据的连续关系时，可以优先思考：

  1. 是否能用哈希表代替排序？
  2. 是否能找到每个结构的唯一入口？
  3. 是否能只从入口遍历，避免从内部节点重复扫描？

“找到唯一入口再展开”是避免嵌套循环退化的重要技巧，也适用于链结构分组、区间连通块和图中的连通分量统计。