128. 最长连续序列

Origin: LeetCode 128

题目描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度。要求时间复杂度 O(n)。

示例

Input: nums = [100, 4, 200, 1, 3, 2] Output: 4 Explanation: 最长连续序列是 [1, 2, 3, 4]，长度 4。

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] Output: 9

约束

• 0 <= nums.length <= 10
• -10^9 <= nums[i] <= 10

关键信息

• 要求 O(n)，不能排序（排序是 O(n log n)）
• 用 Set 存所有数，从每个序列起点开始数
• 序列起点 = num - 1 不在 Set 中

Resolution

我的解法

function longestConsecutive(nums: number[]): number {
    const set = new Set(nums)
    let maxLength = 0
    for (const num of set) {
        if (!set.has(num - 1)) {
            let length = 1
            let cur = num
            while (set.has(cur + 1)) {
                cur++
                length++
            }
            maxLength = Math.max(maxLength, length)
        }
    }
    return maxLength
}

解题思路

Set 去重后，只从序列起点开始数。起点判断：num - 1 不在 Set 中，说明 num 是某个连续序列的开头。

• 遍历 Set（不是 nums），避免重复元素重复检查
• 是起点 → 往后数 num+1, num+2… 直到不在 Set 里
• 不是起点 → 跳过（它一定被某个起点数过了）

踩坑

• 遍历 nums 而不是 set，大量重复元素导致超时（几万个 0）
• 每个元素最多被 while 访问一次，总体 O(n)

复杂度

• 时间：O(n)
• 空间：O(n)