好的，我们这次来详细讲解 LeetCode 第 128 题：最长连续序列（Longest Consecutive Sequence）。

1. 题目描述

题目链接：LeetCode 128

难度：中等

题目描述：

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

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

示例 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
解释：最长数字连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]，长度为 9。

提示：

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

2. 题意分析

题目的核心是：
我们要找的是数值上连续的整数序列，这些整数可以出现在原数组的任意位置，不要求它们在原数组中连续存放。
并且要求算法时间复杂度为 O(n)。

例如：

nums = [100, 4, 200, 1, 3, 2]

排序后是 [1, 2, 3, 4, 100, 200]，连续序列有：

• 1, 2, 3, 4 → 长度 4
• 100 → 长度 1
• 200 → 长度 1

所以最长连续序列长度是 4。

3. 思路演进

3.1 方法一：排序（不符合 O(n) 要求，但容易想到）

如果先排序，再扫描一遍找连续递增序列的最大长度，时间复杂度是 O(n log n)，空间复杂度 O(1)（如果忽略排序的栈开销）。

步骤：

1. 排序数组
2. 遍历数组，如果当前数等于前一个数加 1，则当前连续长度 +1
3. 如果当前数等于前一个数，则跳过（重复数字不增加长度，但不断开序列）
4. 否则重置当前连续长度为 1
5. 记录最大长度

这个方法简单，但题目要求 O(n)，所以排序法不符合要求。

3.2 方法二：哈希集合 + 寻找序列起点（O(n) 解法）

核心思想：
我们只从每个连续序列的起点开始向后扩展，避免重复计算。

如何判断一个数 x 是不是某个连续序列的起点？
如果集合中不存在 x - 1，那么 x 就是一个序列的起点。

步骤：

1. 将所有数字放入哈希集合（去重，且 O(1) 查找）。
2. 遍历数组中的每个数：
   • 检查 num - 1 是否在集合中：
     • 如果不在，说明 num 可能是一个连续序列的起点。
     • 然后从 num 开始，依次检查 num+1, num+2, ... 是否在集合中，计算当前序列长度。
3. 更新最大长度。

为什么这是 O(n) 时间复杂度？
虽然看起来有嵌套循环（外层遍历数组，内层 while 向后扩展），但注意每个数字最多被内层循环访问一次（因为一旦被扩展过，它就不会再作为起点被扩展）。
所以内外层总共遍历次数是 O(n)。

4. 详细步骤演示

以 nums = [100, 4, 200, 1, 3, 2] 为例：

1. 建立集合：{100, 4, 200, 1, 3, 2}
2. 遍历数组：
   • num = 100：
     检查 99 是否在集合？不在 → 是起点。
     向后扩展：101 不在集合 → 序列长度 = 1。
   • num = 4：
     检查 3 是否在集合？在（3 存在）→ 不是起点，跳过。
   • num = 200：
     检查 199 不在集合 → 是起点。
     向后扩展：201 不在集合 → 长度 = 1。
   • num = 1：
     检查 0 不在集合 → 是起点。
     向后扩展：2 在集合，3 在集合，4 在集合，5 不在集合 → 序列 [1,2,3,4] 长度 = 4。
   • num = 3：
     检查 2 在集合 → 跳过。
   • num = 2：
     检查 1 在集合 → 跳过。
3. 最大长度 = max(1, 1, 4) = 4。

5. 代码实现（Python）

def longestConsecutive(nums):
    if not nums:
        return 0
    
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        # 只从序列起点开始计算
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1
            
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1
            
            longest = max(longest, current_streak)
    
    return longest

复杂度分析：

• 时间复杂度：O(n)，每个元素最多被内外层循环访问一次。
• 空间复杂度：O(n)，用于存储哈希集合。

6. 关键点总结

1. 去重：使用集合去重，避免重复数字干扰。
2. 起点判断：通过检查 num - 1 是否在集合中，确保每个序列只被计算一次。
3. O(n) 合理性：虽然代码有嵌套循环，但每个数字最多进入内层循环一次（当它作为序列起点或被起点扩展时），因此整体是 O(n)。

7. 类似题目

• LeetCode 674：最长连续递增序列（数组已排序，简单版）
• LeetCode 485：最大连续 1 的个数（类似但更简单）

这样讲解是否清晰？如果有哪里需要进一步展开或举例，请告诉我！