最长连续序列

更新: 7/4/2026 字数: 0 字 时长: 0 分钟

题目描述

给定一个未排序的整数数组 nums，找出其中「数值连续」的最长序列的长度。这里的连续是指数值上连续（如 1,2,3,4），不要求这些数在原数组中相邻。

要求算法的时间复杂度为 O(n)。

示例：

输入：nums = [100, 4, 200, 1, 3, 2]
输出：4
解释：最长的连续序列是 [1, 2, 3, 4]，长度为 4。
      （100、200 都是孤立的，各自长度只有 1）

思路拆解

先看最直觉的做法：为什么排序不够「优雅」

最容易想到的是先排序再扫一遍：排完序后，相邻元素若差 1 就把当前连续长度 +1，否则重置。这确实能做对，但排序本身就是 ，达不到题目要求的 O(n)。

点击展开暴力解法（排序法，O(n log n)）

function longestConsecutive(nums) {
  if (nums.length === 0) return 0
  const arr = [...new Set(nums)].sort((a, b) => a - b) // 去重 + 排序
  let best = 1, run = 1
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] === arr[i - 1] + 1) run++      // 接上了
    else run = 1                              // 断开，重置
    best = Math.max(best, run)
  }
  return best
}

思路清晰、易写对，但排序把复杂度卡在了 。要做到 O(n)，必须换掉「排序」这一步。

关键转折：只从「序列起点」往后数

如果我们把所有数丢进一个哈希集合 Set，判断「某个数在不在」就变成 。于是可以对每个数尝试往后数：x, x+1, x+2, …，直到断开。

但如果对每个数都这么数，会重复劳动——比如 1,2,3,4 这段，从 1 数一次、从 2 又数一次……最坏退化成 。

核心思路

诀窍是：只从一段连续序列的「起点」开始数。

一个数 x 是起点，当且仅当 x - 1 不在集合里（没有前驱能接到它前面）。

• 若 x - 1 在集合里 → x 不是起点，直接跳过（把统计工作留给真正的起点）。
• 若 x - 1 不在集合里 → x 是起点，从它开始不断查 x+1, x+2, …，数出这一段的长度。

这样每个数最多被访问两次（外层判定起点一次、作为某段内部被延伸时一次），总时间是 O(n)。

一步步看下面的动画

下面的动画用样例 nums = [100, 4, 200, 1, 3, 2] 演示：外层遍历原数组，遇到有前驱的数（如 4、3、2）直接划掉跳过；只有起点（100、200、1）才向后延伸。从 1 出发一路数到 4，得到最长长度 4。可以单步、自动播放或重置。

哈希集合 · 最长连续序列演示

样例：nums = [100, 4, 200, 1, 3, 2]，最长连续序列长度 4

当前阶段：准备最长记录：0

原数组 nums（外层遍历）

100

4

200

1

3

2

哈希集合 Set（升序展示，O(1) 查询）

1

2

3

4

100

200

当前考察数 x非起点 · 跳过本段连续数最终最长段

目标：找出最长的「数值连续」序列长度（元素在原数组中不要求相邻）。样例 [100, 4, 200, 1, 3, 2] 的答案是 4，对应 1,2,3,4。

步骤 0 / 14

完整代码

/**
 * 最长连续序列：哈希集合 + 只从起点向后延伸，时间 O(n)。
 */
function longestConsecutive(nums) {
  // 放进 Set，去重并支持 O(1) 查询
  const set = new Set(nums)
  let best = 0

  for (const x of set) {
    // 只有 x-1 不存在时，x 才是某段连续序列的起点
    if (!set.has(x - 1)) {
      let cur = x
      let run = 1
      // 从起点不断向后延伸
      while (set.has(cur + 1)) {
        cur++
        run++
      }
      best = Math.max(best, run)
    }
  }

  return best
}

// 示例
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])) // 4

易错点

• 必须加 if (!set.has(x - 1)) 这道「起点」判断，否则每段会被从中间反复统计，退化为 。
• 建议直接遍历 set 而不是原数组 nums，可自动跳过重复元素、减少无谓的起点判断。
• 空数组要返回 0；best 初始化为 0 即可自然覆盖这一情况。
• 内层用 while (set.has(cur + 1))，别写成对 nums 做线性查找——那样每次查询是 ，整体又退化了。

复杂度分析

解法	时间复杂度	空间复杂度	说明
排序 + 扫描			简单但不满足 O(n) 要求
每个数都向后数			缺少起点判断，重复统计
哈希集合 + 起点判断			每个数最多被访问两次

为什么是 O(n)？内层 while 的总执行次数等于「所有连续段的总长度」，而每个数只会作为某一段的内部元素被延伸一次；外层对每个数做一次 的起点判断。两部分相加仍是线性。

边界与易错点

• 空数组： nums = [] 返回 0。
• 含重复元素： 如 [1, 2, 2, 3]，Set 去重后按 1,2,3 统计，结果 3，重复值不会干扰。
• 单个元素： [10] 返回 1。
• 负数与不连续大数： 如 [0, -1, 1, 100]，-1,0,1 连成一段长度 3，100 孤立长度 1，答案 3；负数作为 Set 的键同样是 查询。
• 不要在内层用数组线性查找： 必须依赖 Set 的 成员判断，否则复杂度会被打回 。
• 谨防「从中间统计」： 起点判断是整个 O(n) 保证的核心，删掉它就退化了。