LeetCode 128最长连续序列 | 哈希表与集合的巧妙运用引言最长连续序列Longest Consecutive Sequence是 LeetCode 第 128 题难度为 Hard是哈希表应用中的经典难题。题目要求在未排序的整数数组中找到最长连续序列的长度其中连续序列指的是元素值连续的序列。例如对于数组 [100, 4, 200, 1, 3, 2]最长的连续序列是 [1, 2, 3, 4]长度为 4。这道题的难点在于如何在 O(n) 时间复杂度内解决而不是简单的排序后遍历。排序解法的时间复杂度是 O(n log n)虽然也能通过但哈希表方法可以将时间复杂度降低到 O(n)展现了对问题更深入的理解。问题分析题目描述给定一个未排序的整数数组 nums找出最长连续序列的长度。要求时间复杂度为 O(n)。例如输入 nums [100, 4, 200, 1, 3, 2]最长的连续序列是 [1, 2, 3, 4]所以返回 4。输入 nums [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]最长连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]返回 9。问题特点这道题的关键挑战在于时间复杂度的要求。如果允许 O(n log n) 的时间复杂度可以先对数组排序然后使用一次线性遍历找出最长连续序列。但题目要求 O(n) 的时间复杂度这意味着我们不能使用排序。哈希表方法通过将所有元素存入集合Python 的 set 或哈希表然后利用集合的 O(1) 查找能力跳过不可能是序列起点的元素从而在 O(n) 时间内解决问题。关键洞察解决这个问题的关键洞察是对于序列中的任意一个元素如果不是序列的起点即存在 num-1 在集合中那么它不可能是新的连续序列的起点因为它的前面还有更小的元素。例如在序列 [1, 2, 3, 4] 中1 是起点因为 0 不在集合中但 2、3、4 都不是起点因为它们各自的前一个元素都在集合中。因此当我们遍历到 2 时我们可以跳过它因为以 2 为起点的序列一定比以 1 为起点的序列短。这种优化使得我们在最坏情况下所有元素都是连续序列的一部分只需要遍历一次。哈希表解法解法思路def longestConsecutive(nums): num_set set(nums) longest 0 for num in num_set: if num - 1 not in num_set: current num streak 1 while current 1 in num_set: current 1 streak 1 longest max(longest, streak) return longest这段代码展示了哈希表解法的完整实现。首先将所有元素存入集合 num_set集合的查找操作是 O(1)。然后遍历集合中的每个元素对于每个可能是起点的元素num-1 不在集合中计算以该元素为起点的连续序列长度。最后返回所有序列长度中的最大值。算法流程算法的工作流程如下对于每个元素 num首先检查它是否是序列的起点。判断方法是检查 num-1 是否存在于集合中。如果不存在说明 num 是一个可能的序列起点我们从它开始向后遍历计算连续序列的长度。如果存在说明 num 不是序列的起点可以跳过。向后遍历使用 while 循环每次检查 current 1 是否在集合中如果在就继续向后并增加计数。当遇到不连续的元素时停止此时我们已经计算出了以 num 为起点的最长连续序列长度。为什么这样能保证 O(n)粗略看算法中有一个嵌套的 while 循环可能会让人以为是 O(n²)。但仔细分析可以发现每个元素最多被访问两次一次是在外层 for 循环中判断它是否是起点一次是在内层 while 循环中被计数。考虑最坏情况数组是 [1, 2, 3, ..., n]一个完整的连续序列。外层循环会遍历所有 n 个元素但只有第一个元素1会被判断为起点并进入内层循环。内层循环会访问所有 n 个元素。所以总访问次数是 O(n)。一般地每个连续序列的起点会进入内层循环并访问序列的所有元素每个非起点的元素只被外层循环访问一次。所以总时间复杂度是 O(n)。并查集解法并查集思路这个问题也可以用并查集Union Find来解决。并查集是一种处理不相交集合合并和查询的数据结构特别适合处理连通性相关的问题。class UnionFind: def __init__(self, nums): self.parent {num: num for num in nums} self.size {num: 1 for num in nums} def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return if self.size[rx] self.size[ry]: rx, ry ry, rx self.parent[ry] rx self.size[rx] self.size[ry] def longestConsecutive_union(nums): if not nums: return 0 uf UnionFind(nums) for num in nums: if num 1 in uf.parent: uf.union(num, num 1) return max(uf.size.values())并查集方法的核心思想是将连续的元素合并到同一个集合中。首先每个元素是一个单独的集合。然后遍历每个元素如果 num1 也在数组中将 num 和 num1 合并到同一个集合。最后返回最大集合的大小即最长连续序列的长度。并查集的时间复杂度并查集的查询和合并操作在路径压缩和按秩合并的优化下几乎是常数时间的。因此并查集方法的时间复杂度也是 O(n α(n)) ≈ O(n)空间复杂度是 O(n)。算法复杂度分析哈希表法时间复杂度为 O(n)空间复杂度为 O(n)。虽然内层循环在最坏情况下会遍历整个数组但每个元素最多被遍历两次总操作数是线性的。并查集法时间复杂度为 O(n α(n)) ≈ O(n)空间复杂度为 O(n)。α(n) 是 Ackermann 函数的反函数在实践中可以认为是常数。排序法对比时间复杂度为 O(n log n)空间复杂度为 O(1)如果可以原地排序或 O(n)。虽然不是最优的但排序法更简单适用于对空间有要求但对时间要求不严格的场景。边界情况处理空数组当数组为空时最长连续序列长度为 0。代码正确处理了这种情况因为集合为空外层循环不会执行longest 保持为 0。单元素数组当数组只有一个元素时最长连续序列长度为 1。该元素是起点没有 num-1内层循环会立即结束返回 1。全相同元素当所有元素相同时如 [5, 5, 5, 5]最长连续序列长度为 1。每个元素都不是起点因为 4 不在集合中但内层循环也会立即结束返回 1。无连续序列当没有任何连续元素时如 [100, 200, 300]最长连续序列长度为 1。每个元素都是起点但内层循环都会立即结束。测试用例def test_longest_consecutive(): assert longestConsecutive([100, 4, 200, 1, 3, 2]) 4 assert longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) 9 assert longestConsecutive([]) 0 assert longestConsecutive([1]) 1 assert longestConsecutive([1, 2, 3, 4, 5]) 5 assert longestConsecutive([5, 4, 3, 2, 1]) 5 assert longestConsecutive([1, 2, 0, 1]) 3 assert longestConsecutive([0, 0]) 1 print(所有测试用例通过)实际应用场景最长连续序列问题在现实中有很多应用。在金融领域可以用来检测连续涨跌幅的记录。在游戏开发中可以用来计算连击次数或连续得分。在数据分析中可以用来识别连续出现的模式或异常。从更广泛的角度看这个问题本质上是在处理连续性的检测。连通性是图论和计算机科学中的核心概念很多问题都可以归结为连通性的检测和计算。并查集作为处理连通性的利器在很多复杂问题中都有应用如社交网络中的朋友圈划分、图像处理中的连通区域标记等。总结最长连续序列问题展示了几种不同算法设计思路的对比排序法的简洁性、哈希表法的高效性、以及并查集法的通用性。哈希表法通过只从序列起点开始的优化将看似 O(n²) 的问题转化为 O(n)体现了对问题特点的深入理解。在面试中如果被问到这道题应该首先提出排序的简单方案然后分析其不足最后提出哈希表的优化方案。这种由浅入深的解决思路能给面试官留下好的印象展示你的问题分析能力和算法优化能力。希望通过本文的讲解读者能够深入理解这道题的多种解法及其背后的算法思想。
