哈希算法题目：最长连续序列

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

解题过程：

1. 问题理解
   我们需要在无序数组中找到最长的连续数字序列。比如数组 [100, 4, 200, 1, 3, 2] 中，最长的连续序列是 [1, 2, 3, 4]，长度为 4。注意序列中的数字在原数组中不要求连续出现。

2. 关键思路

• 使用哈希集合存储所有数字，实现 O(1) 时间查询
• 对于每个数字，只有当它是序列的起点时才开始向后查找连续序列
• 如何判断起点？如果当前数字的前一个数（num-1）不在集合中，说明它是起点

3. 详细步骤
   步骤1：创建哈希集合

• 将所有数字存入哈希集合，这样查询某个数是否存在只需 O(1) 时间

步骤2：遍历集合寻找起点

• 遍历哈希集合中的每个数字
• 对于当前数字 num，检查 num-1 是否在集合中
• 如果 num-1 不存在，说明 num 是某个连续序列的起点

步骤3：扩展连续序列

• 从起点 num 开始，不断检查 num+1、num+2... 是否在集合中
• 每找到一个连续数，序列长度加1
• 直到遇到不连续的数字为止

步骤4：更新最大长度

• 比较当前序列长度与已知最大长度，取较大值

4. 示例演示
   以数组 [100, 4, 200, 1, 3, 2] 为例：

• 哈希集合：{100, 4, 200, 1, 3, 2}
• 遍历过程：
  • 数字1：1-1=0不在集合，是起点 → 向后找2、3、4都在 → 序列长度4
  • 数字2：2-1=1在集合，不是起点 → 跳过
  • 数字3：3-1=2在集合，不是起点 → 跳过
  • 数字4：4-1=3在集合，不是起点 → 跳过
  • 数字100：100-1=99不在集合，是起点 → 向后找101不在 → 序列长度1
  • 数字200：200-1=199不在集合，是起点 → 向后找201不在 → 序列长度1
• 最长序列长度为4

5. 复杂度分析

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

6. 边界情况处理

• 空数组：直接返回0
• 所有数字相同：序列长度为1
• 数字有重复：哈希集合自动去重，不影响正确性

这种方法通过哈希集合的快速查询特性，避免了排序的 O(nlogn) 时间复杂度，实现了最优的 O(n) 解法。