最长连续序列问题

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

示例：
输入：nums = [100, 4, 200, 1, 3, 2]
输出：4
解释：最长连续序列是 [1, 2, 3, 4]，长度为 4。

解题思路

1. 暴力解法（不可行）

   • 对数组排序后扫描，但排序需 O(n log n)，不满足 O(n) 要求。
   • 对于每个数字，检查其后续数字是否存在，但检查存在性需 O(n)，整体 O(n²)。

2. 哈希集合优化

   • 核心思路：仅从序列起点开始统计长度，避免重复计算。
   • 步骤：
     a. 将所有数字存入哈希集合（O(n)）。
     b. 遍历集合，若当前数字 x 的前驱 x-1 不存在，则 x 是序列起点。
     c. 从起点 x 开始，依次检查 x+1, x+2... 是否在集合中，统计长度。
     d. 更新最大长度。

详细步骤

1. 预处理

   num_set = set(nums)  # 去重并实现 O(1) 查询
   

2. 遍历集合

   • 跳过非起点的数字（若 x-1 存在，则 x 不是起点）。
   • 对每个起点 x，循环检查 x+1, x+2... 是否存在，计数 current_length。

3. 示例推演

   • 数组：[100, 4, 200, 1, 3, 2]
   • 集合：{1, 2, 3, 4, 100, 200}
   • 遍历过程：
     • 数字 1：前驱 0 不存在 → 起点，向后找到 2,3,4 → 长度 4。
     • 数字 2：前驱 1 存在 → 跳过。
     • 数字 3：前驱 2 存在 → 跳过。
     • 数字 4：前驱 3 存在 → 跳过。
     • 数字 100：前驱 99 不存在 → 起点，向后无连续 → 长度 1。
     • 数字 200：前驱 199 不存在 → 起点，向后无连续 → 长度 1。
   • 最长长度：4。

代码实现

def longestConsecutive(nums):
    if not nums:
        return 0
    
    num_set = set(nums)
    max_length = 0
    
    for num in num_set:
        # 仅当 num 是序列起点时处理
        if num - 1 not in num_set:
            current_num = num
            current_length = 1
            
            # 向后扩展序列
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1
            
            max_length = max(max_length, current_length)
    
    return max_length

复杂度分析

• 时间复杂度：O(n)。每个数字最多被访问两次（一次在集合中，一次在序列扩展中）。
• 空间复杂度：O(n)，用于存储哈希集合。

关键点

• 利用哈希集合 O(1) 查询特性。
• 仅从序列起点开始统计，避免重复计算。
• 外层循环遍历集合而非原数组（避免重复数字干扰）。