128. 最长连续序列

题目链接（中等）

题目描述

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

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

数据范围：

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

示例

示例 1：

输入： nums = [100,4,200,1,3,2]
输出： 4
解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入： nums = [0,3,7,2,5,8,4,6,0,1]
输出： 9

示例 3：

输入： nums = [1,0,1,2]
输出： 3

方法一：排序 + 遍历

思路及解法

最直观的思路：先排序，再顺序扫描，看连续的数字能延伸到多长。

具体步骤：

1. 对数组排序；
2. 遍历排序后的数组，用 cur 记录当前连续段的长度：
   • 若 nums[i] == nums[i-1]：重复元素，跳过（不影响连续长度）；
   • 若 nums[i] == nums[i-1] + 1：连续，cur += 1；
   • 否则：连续中断，更新答案并重置 cur = 1；
3. 循环结束后再更新一次答案（因为最长连续段可能一直到数组末尾）。

排序法的思路最简单，但时间复杂度是 $O(n \log n)$，不满足题目的 $O(n)$ 要求。面试时可以作为开场思路，再优化到哈希法。

代码

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0

        nums.sort()
        longest = 1
        cur = 1

        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                continue                  # 重复元素，跳过
            elif nums[i] == nums[i - 1] + 1:
                cur += 1                  # 连续，长度 +1
            else:
                longest = max(longest, cur)
                cur = 1                   # 中断，重新开始

        return max(longest, cur)

复杂度分析

• 时间复杂度：$O(n \log n)$，主要开销是排序。
• 空间复杂度：$O(1)$ 或 $O(n)$，取决于排序实现。

方法二：哈希集合 + 只从起点扩展

思路及解法

朴素思路：枚举数组中的每个数 x，尝试匹配 x+1, x+2, ... 是否存在，把连续的最长长度记下来。

用哈希集合存所有数，判断某个数是否存在就是 $O(1)$。但这样还有问题：如果每次都从 x 开始扩展，会重复枚举。

关键优化：对于一个连续序列 x, x+1, ..., x+y，从 x+1 或 x+2 开始扩展的结果一定不会优于从 x 开始。因此只需要从每个连续段的起点开始扩展。

如何判断 x 是不是起点？ 检查 x - 1 是否存在于集合中：

• 若 x - 1 不在集合里，说明 x 是某个连续段的起点，从这里开始往后数；
• 若 x - 1 在集合里，说明 x 不是起点，跳过（前面会有更小的数作为起点）。

为什么总时间是 $O(n)$？

• 外层遍历哈希集合一次，是 $O(n)$；
• 内层 while 只在「起点」时才进入，每个数最多被内层访问一次；
• 所以整体是 $O(n)$。

直觉理解：把每个连续段只看一次，且只看它最小的那个数（起点）。其他数都被跳过，所以不会重复劳动。

代码

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        num_set = set(nums)
        ans = 0

        for num in num_set:
            # 只从每个连续段的起点开始扩展
            if num - 1 not in num_set:
                cur = num
                count = 1
                while cur + 1 in num_set:
                    cur += 1
                    count += 1
                ans = max(ans, count)

        return ans

复杂度分析

• 时间复杂度：$O(n)$，每个数最多被访问两次（一次外层判断、一次内层扩展）。
• 空间复杂度：$O(n)$，哈希集合存储所有元素。

相关题目

• LC 674. 最长连续递增序列（要求在原数组中连续）
• LC 300. 最长递增子序列（不要求连续，但要求严格递增）