LeetCode 最长连续序列：哈希集合的巧妙解法（Python）

题目描述给定一个未排序的整数数组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解题思路最直观的想法是排序后遍历但排序的时间复杂度为O(n log n)不满足题目对O(n)的要求。要实现线性时间复杂度关键在于避免对每个元素都进行重复的“向前/向后”查找。核心思路将所有数字存入一个哈希集合set中实现O(1)的查找。遍历集合中的每个数字但只从“序列的起点”开始计数。如何判断一个数字是否是序列的起点如果num - 1不在集合中说明num可能是一个连续序列的起始数字。对于每个起点不断检查num 1,num 2... 是否在集合中从而计算出以该数字为起点的连续序列长度。记录遍历过程中遇到的最大长度。这个算法之所以是O(n)是因为每个数字最多被访问两次一次在外部循环中判断是否为起点一次在内层 while 循环中作为连续序列的一部分被检查且集合操作是O(1)。算法执行过程示例为了更直观地理解算法的执行逻辑我们以题目中的数组[100, 4, 200, 1, 3, 4, 2]为例逐步分析算法的执行过程。第一步去重并构建哈希集合首先将数组转换为集合去除重复元素原始数组: [100, 4, 200, 1, 3, 4, 2] 去重后的集合: {100, 4, 200, 1, 3, 2}第二步遍历集合寻找序列起点并计算长度接下来遍历集合中的每个元素判断是否为连续序列的起点即num - 1不在集合中元素 100检查 99 是否在集合中 → 不在 → 100 是起点。以 100 为起点向后查找101 不在集合中 → 序列结束。序列为 [100]长度为 1。元素 4检查 3 是否在集合中 → 在 → 4 不是起点跳过。元素 200检查 199 是否在集合中 → 不在 → 200 是起点。以 200 为起点向后查找201 不在集合中 → 序列结束。序列为 [200]长度为 1。元素 1检查 0 是否在集合中 → 不在 → 1 是起点。以 1 为起点向后查找2 在集合中 → 长度1当前长度2。继续查找3 在集合中 → 长度1当前长度3。继续查找4 在集合中 → 长度1当前长度4。继续查找5 不在集合中 → 序列结束。序列为 [1, 2, 3, 4]长度为 4。元素 3检查 2 是否在集合中 → 在 → 3 不是起点跳过。元素 2检查 1 是否在集合中 → 在 → 2 不是起点跳过。第三步更新并返回最大长度遍历过程中记录的最大长度为 4来自以 1 为起点的序列。复杂度分析验证在这个例子中元素 100、200、1 分别作为起点被完整访问一次外层循环判断 内层 while 循环。元素 4、3、2 仅在外层循环中被访问一次判断不是起点后跳过。每个元素最多被访问两次符合 O(n) 的时间复杂度分析。通过这个具体的例子我们可以清晰地看到算法如何通过“只从序列起点开始计数”的策略避免了重复计算同时保证了线性时间复杂度。代码实现Python以下是基于上述思路的 Python 实现from typing import List class Solution: def longestConsecutive(self, nums: List[int]) - int: # 记录最长序列长度 max_length 0 # 将数组转换为集合用于 O(1) 查找同时去重 num_set set(nums) for num in num_set: # 只有当 num 是某个连续序列的起点时才进行内层循环 if num - 1 not in num_set: current_length 1 current_num num # 向后查找连续的数字 while current_num 1 in num_set: current_length 1 current_num 1 # 更新最大长度 max_length max(max_length, current_length) return max_length代码解析去重与快速查找num_set set(nums)将列表转换为集合既去除了重复元素又为后续的in操作提供了O(1)的时间复杂度。寻找序列起点if num - 1 not in num_set:是算法的关键。如果num - 1存在于集合中那么num肯定不是当前连续序列的起点我们可以跳过它因为以num - 1为起点的序列一定会覆盖num。计算序列长度对于每个起点使用while循环不断检查current_num 1是否在集合中并累加长度。更新最大值每次计算完一个序列的长度后用max函数更新全局最大值。复杂度分析时间复杂度O(n)。虽然代码中有嵌套循环但每个数字最多被访问两次一次在外层循环判断起点一次在内层循环作为序列的一部分因此总体是线性的。空间复杂度O(n)。用于存储哈希集合。总结本题的难点在于如何在线性时间内解决问题。通过使用哈希集合和“只从序列起点开始计数”的巧妙策略我们避免了排序也避免了为每个元素进行重复的线性搜索。这是一种典型的“用空间换时间”的策略也是处理数组查找类问题的常用技巧。