最长连续序列

题目描述：给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。要求算法的时间复杂度为 O(n)。

解题过程：

1. 理解问题核心

   • 我们要找的是"数值连续"的序列，比如 [1,2,3,4]
   • 序列中的数字在原数组中可以不连续出现
   • 要求时间复杂度 O(n)，所以不能先排序（排序至少 O(n log n)）

2. 关键观察

   • 对于任意连续序列，它一定有起点（序列中最小的数）
   • 起点的特征：nums 中不存在比它小 1 的数（即 num-1 不在数组中）
   • 从这个起点开始，我们可以不断检查 num+1 是否在数组中，从而确定序列长度

3. 算法思路

   • 用哈希集合存储所有数字，实现 O(1) 的查找
   • 遍历数组中的每个数字
   • 对于每个数字，如果它是某个序列的起点（即 num-1 不在集合中），就开始向后扩展序列
   • 记录遇到的最长序列长度

4. 详细步骤

   def longestConsecutive(nums):
       if not nums:
           return 0
   
       num_set = set(nums)  # 转换为集合，O(n)
       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
   

5. 复杂度分析

   • 时间复杂度：O(n)
     • 创建集合：O(n)
     • 外层循环：每个元素最多被访问一次
     • 内层while：每个元素最多被访问一次（只有作为起点时才会进入内层循环）
   • 空间复杂度：O(n)，用于存储哈希集合

6. 举例说明
   对于 nums = [100, 4, 200, 1, 3, 2]：

   • 集合：{100, 4, 200, 1, 3, 2}
   • 处理 100：100-1=99 不在集合中，向后扩展得到序列 [100]，长度 1
   • 处理 4：4-1=3 在集合中，跳过
   • 处理 200：200-1=199 不在集合中，向后扩展得到序列 [200]，长度 1
   • 处理 1：1-1=0 不在集合中，向后扩展得到序列 [1,2,3,4]，长度 4
   • 最终结果：4

这种方法确保了每个数字最多被处理两次，达到了 O(n) 的时间复杂度要求。