手帐 Blog

主题

复盘 · LC 128 最长连续序列 ​

题目 ​

题意 ​

给定未排序整数数组 nums，求其中数字能构成的最长连续序列的长度（序列元素在数组中不必相邻，但数值要连续）。

  • 要求尽量 O(n) 时间。
  • 数字可重复；连续指 x, x+1, x+2, …。

边界：空数组 → 0；全重复；负数与跨零；多个互不重叠的长段。

涉及算法 ​

标签一句话
哈希 SetO(1) 判断 x±1 是否存在
只从段起点扩展仅当 x-1 不在集合时，才向右数长度 → 总扩展 O(n)

教程对照：09 · 哈希表进阶（最长连续序列是该篇另一道核心例）。

评价我的解法 ​

有两版：先自研 Map 递推，81/85 TLE；再按标准套路用 Set + 段起点，默写通过。

第一版（超时） ​

我的代码（摘自 128-最长连续序列/index.js，不含测例）：

javascript
var longestConsecutive = function (nums) {
  const resMap = new Map();
  for (const num of nums) {
    const count = resMap.get(num) || 0;
    if (!count) {
      resMap.set(num, 1);
    }
  }
  const countList = [];
  for (const key of resMap.keys()) {
    let len = 1;
    let nextKey = parseInt(key) + 1;
    while (true) {
      const nextValue = resMap.get(nextKey);
      if (!nextValue) {
        break;
      } else if (nextValue === 1) {
        len++;
        nextKey++;
      } else {
        len += nextValue;
        break;
      }
    }
    resMap.set(key, len);
    countList.push(len);
  }
  if (countList.length === 0) {
    return 0;
  } else {
    return Math.max(...countList);
  }
};

问题很集中：

  1. 对每个 key 都向右扫：中间点（如序列里的 2、3）也会再走一遍后缀，最坏接近 O(n²)，对应注释里的「超出时间限制」。
  2. 想用「已算长度」加速（nextValue !== 1 时累加），但遍历顺序不是拓扑序，memo 不完整，既没真正降到 O(n)，逻辑也难讲清。
  3. Map 实际只当「去重集合」用；parseInt(key) 多余（数字 key 本身可用）。

方向感有：去重 + 顺着 +1 数长度。缺的是**「只从连续段左端点起步」**这一刀。

第二版（看答案后默写） ​

我的代码（摘自 128-最长连续序列/index2.js，不含测例）：

javascript
var longestConsecutive = function (nums) {
  let maxLen = 0;
  const numSet = new Set(nums);
  for (const num of numSet) {
    if (!numSet.has(num - 1)) {
      let len = 1;
      let i = 1;
      while (true) {
        let hasNext = numSet.has(num + i);
        if (!hasNext) {
          break;
        }
        len++;
        i++;
      }
      maxLen = Math.max(maxLen, len);
    }
  }
  return maxLen;
};

对在哪：!has(num - 1) 保证每段只从起点扩展一次，总 while 次数 O(n)。能独立默写说明 TLE 之后把关键吃进去了。

可再干净一点：while (numSet.has(num + len)) len++，少一个 i 变量。

小结：第一版暴露「会哈希、不会卡复杂度」；第二版已是面试标准解。以后这类题先问：怎样保证每个元素只被扩展常数次？

最佳题解 ​

与 index2 同套路的清爽写法：

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue; // 不是段起点
    let len = 1;
    while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  return best;
};
  • 时间 O(n)，空间 O(n)。
  • 为何更优：去重 + 仅起点扩展，避免对中间点重复扫描；比排序 O(n log n) 更贴题面「尽量线性」。

关联题目 ​

题为何相关
298. 二叉树最长连续序列「连续」换到树路径
674. 最长连续递增序列要求下标连续，变成一维扫描
300. 最长递增子序列同是「最长」，约束从数值连续变成递增子序列

一句话带走 ​

最长连续序列：丢进 Set，只从没有 x-1 的 x 往右数；每个数最多被访问常数次，才是真正的 O(n)。