最长连续序列 - Stellar Observer Protocol

498 字

2 分钟

最长连续序列

2025-08-13

Algorithms

数组

/

哈希表

/

并查集

题目描述#

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路#

哈希集合预处理：
- 将数组元素存入哈希集合（去重+O(1)查询）
- 消除重复元素干扰
连续序列起点检测：
- 遍历集合元素
- 仅当 num-1 不存在时，将 num 视为序列起点
序列长度计算：
- 从起点开始，循环查询 num+1 是否存在
- 计数连续存在的数字个数
全局最大值更新：
- 比较并记录最长序列长度

关键洞察#

起点筛选原理：
- 序列起点必有 num-1 不存在
- 避免重复计算相同序列
哈希集合优势：
- O(1) 时间检测元素存在性
- 空间换时间提高效率
连续性检测机制：
- 从起点单向扩展（num++）
- 自然覆盖最长连续序列
去重必要性：
- 重复元素不影响序列长度
- 集合自动处理重复值

复杂度分析#

指标	说明
时间复杂度	O(n)：每个元素最多被访问两次（起点检测+序列扩展）
空间复杂度	O(n)：哈希集合存储所有元素

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
const longestConsecutive = (nums) => {
6
    // 创建哈希集合
7
    const numSet = new Set(nums);
8
    let maxStreak = 0;
9
    for (const num of numSet) {
10
        // 仅当 num 是序列起点时处理
11
        if (!numSet.has(num - 1)) {
12
            let currentNum = num;
13
            let currentStreak = 1;
14
            // 扩展连续序列
15
            while (numSet.has(currentNum + 1)) {
16
                currentNum++;
17
                currentStreak++;
18
            }
19
            // 更新全局最大值
20
            maxStreak = Math.max(maxStreak, currentStreak);
21
        }
22
    }
23
    return maxStreak;
24
};