哈希集合解决最长连续序列问题的O(n)算法

1. 最长连续序列问题解析

这道题在LeetCode上编号128，属于中等难度但实际面试中出现频率极高的题目。题目要求我们从一个未排序的整数数组中找到数字连续的最长序列长度，且要求算法时间复杂度为O(n)。乍看简单，但其中暗藏多个考察点。

我第一次遇到这个问题时，第一反应是用排序解决。把数组排序后找最长连续序列确实可行，但排序本身就需要O(nlogn)时间，不满足题目要求。后来在面试官提示下才意识到，这道题的精髓在于如何利用哈希集合的特性来突破常规思维。

2. 核心解法与优化思路

2.1 哈希集合的妙用

最优雅的解法是利用哈希集合（HashSet）来实现O(n)时间复杂度。具体思路是：

1. 首先将所有数字存入哈希集合，这一步耗时O(n)
2. 然后遍历数组中的每个数字，对于每个数字，检查它是否是某个连续序列的起点
3. 如果是起点，则向后查找连续的数字，统计序列长度
4. 最终返回找到的最大长度

关键在于如何判断一个数字是否是序列起点——只需检查哈希集合中是否存在当前数字减一的值。如果不存在，说明当前数字就是一个序列起点。

def longestConsecutive(nums): num_set = set(nums) max_length = 0 for num in num_set: 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

2.2 时间复杂度分析

虽然代码中有嵌套循环，但实际时间复杂度确实是O(n)。因为内层while循环只有在遇到序列起点时才会执行，且数组中的每个数字最多被访问两次（一次加入集合，一次在遍历中检查），所以总体时间复杂度是O(2n)即O(n)。

3. 实现细节与边界处理

3.1 空数组处理

在实际编码中，必须考虑输入数组为空的情况。这时候应该直接返回0，否则后续操作可能引发异常。

if not nums: return 0

3.2 重复元素处理

题目没有说明数组元素是否唯一，但我们的解法已经天然处理了重复元素——因为使用了集合存储，重复元素会被自动去重。

3.3 内存优化

虽然题目没有明确空间复杂度要求，但使用集合确实需要O(n)的额外空间。如果严格要求O(1)空间，可以考虑在原数组上修改标记，但这样会破坏原始数据，且实现起来更复杂。

4. 常见错误与调试技巧

4.1 错误解法示例

很多初学者会尝试这样的解法：

1. 对数组排序
2. 遍历排序后的数组，统计连续序列长度

虽然这个解法能得到正确答案，但时间复杂度是O(nlogn)，不符合题目要求。在面试中提出这种解法通常会被要求优化。

4.2 调试技巧

当实现哈希集合解法时，常见问题包括：

1. 忘记处理空数组
2. 错误判断序列起点（应该检查num-1而非num+1）
3. 重复计算序列长度

调试时可以打印中间变量：

print(f"Checking {num}, is start: {num - 1 not in num_set}") print(f"Current sequence: {current_num}, length: {current_length}")

5. 变种问题与实际应用

5.1 变种问题

1. 返回最长序列本身而非长度
2. 允许序列中有固定间隔（如允许间隔不超过k）
3. 二维矩阵中的最长连续序列

5.2 实际应用场景

这个问题看似抽象，但实际上有很多现实应用：

1. 用户行为分析：找出连续登录天数
2. 库存管理：识别连续的产品序列号
3. 时间序列分析：检测连续事件

6. 算法比较与选择

6.1 排序法 vs 哈希法

虽然哈希法理论性能更好，但对于小规模数据（n<1000），排序法的实际运行时间可能更短，因为哈希操作有常数开销。

6.2 并查集解法

这个问题也可以用并查集(Union-Find)解决，虽然时间复杂度也是O(n)，但实现起来更复杂，适合需要频繁合并集合的场景。

7. 代码优化与语言特性

7.1 Python特定优化

在Python中，集合操作非常高效。但要注意：

1. 使用set()而非{}创建空集合
2. 集合查找是O(1)平均时间复杂度
3. 对于极大数组，考虑使用更节省内存的数据结构

7.2 Java实现要点

在Java中，HashSet的实现略有不同：

Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); }

Java的自动装箱/拆箱可能带来额外开销，对于性能敏感场景可以考虑使用原始类型集合库。

8. 面试技巧与准备建议

这道题是面试高频题，准备时应注意：

1. 理解问题本质：连续≠相邻，序列≠子数组
2. 明确时间复杂度的计算方式
3. 准备多种解法并比较优劣
4. 考虑边界条件和异常情况

在面试中，建议先提出排序解法，再优化到哈希解法，展示思考过程。可以主动讨论时间/空间复杂度权衡。

9. 性能测试与实测数据

我用Python对不同解法进行了性能测试（数组大小1e6）：

结果显示哈希法确实最快，但要注意测试数据特性会影响结果。对于包含大量连续序列的数组，哈希法的优势更明显。

10. 扩展学习与相关题目

为了彻底掌握这类问题，建议练习以下相关题目：

1. LeetCode 674.最长连续递增序列
2. LeetCode 300.最长上升子序列
3. LeetCode 1027.最长等差数列

这些题目都有相似的解题模式，但各自有不同的约束条件和优化点。通过对比学习可以加深对序列处理问题的理解。

我在实际刷题中发现，这类序列问题通常有几种核心解法：

1. 排序+遍历
2. 哈希集合/映射
3. 动态规划
4. 滑动窗口

每种方法适用于不同的约束条件，理解它们的适用场景是解题的关键。对于最长连续序列问题，哈希集合无疑是最优雅高效的解法。