1. 问题背景与核心挑战这道题出现在LeetCode热题100中绝非偶然。作为一道中等难度的题目它完美融合了基础数据结构知识和巧妙的算法思维。我在第一次遇到这个问题时曾天真地以为用简单的排序就能解决直到面对[100, 4, 200, 1, 3, 2]这个测试用例才恍然大悟——原来O(n)的解法才是这道题的精华所在。问题的核心在于给定一个未排序的整数数组nums我们需要找出数字连续的最长序列的长度。这里的连续指的是数值连续而不是数组中的位置连续。例如对于[100, 4, 200, 1, 3, 2]最长连续序列是[1, 2, 3, 4]长度为4。1.1 暴力解法的陷阱大多数人的第一反应包括当初的我可能是这样的先对数组排序然后遍历查找最长连续序列用Python实现的话大概是这样def longestConsecutive(nums): if not nums: return 0 nums.sort() max_len 1 current_len 1 for i in range(1, len(nums)): if nums[i] nums[i-1] 1: current_len 1 elif nums[i] nums[i-1]: continue else: max_len max(max_len, current_len) current_len 1 return max(max_len, current_len)这个解法看似合理但实际上存在两个关键问题时间复杂度是O(nlogn)因为排序操作主导了时间复杂度题目明确要求设计一个O(n)的算法1.2 哈希集合的妙用要实现O(n)的时间复杂度我们必须抛弃排序的思路。这时候哈希集合(set)就派上用场了。哈希集合的查找操作平均时间复杂度是O(1)这为我们设计线性算法提供了可能。核心思路是先将所有数字存入哈希集合对于集合中的每个数字检查它是否是某个连续序列的起点如果是起点则向后查找连续的数字计算序列长度2. 最优解法实现与细节2.1 算法框架基于上述思路我们可以构建如下算法框架def longestConsecutive(nums): num_set set(nums) max_len 0 for num in num_set: # 检查是否是序列起点 if num - 1 not in num_set: current_num num current_len 1 # 向后查找连续数字 while current_num 1 in num_set: current_num 1 current_len 1 max_len max(max_len, current_len) return max_len2.2 关键点解析这个算法的精妙之处在于如何高效判断一个数字是否是序列起点起点判断只有当num-1不在集合中时num才被视为一个序列的起点。这确保了每个序列只被处理一次。序列扩展一旦确认是起点就不断检查num1、num2...是否在集合中直到序列中断。时间复杂度虽然看起来有嵌套循环但实际上每个数字最多被访问两次一次在外部循环一次在内部while循环所以整体是O(n)复杂度。2.3 边界情况处理在实际编码中有几个边界情况需要特别注意空数组输入为空时应该返回0重复数字使用集合自动去重负数处理算法对正负整数都适用大数测试确保不会因为数字太大导致性能问题3. 算法优化与变种3.1 早期终止优化在某些情况下我们可以提前终止算法。例如当剩余未处理的数字数量已经小于当前找到的最大长度时就不需要继续处理了def longestConsecutive(nums): num_set set(nums) max_len 0 for num in num_set: if num - 1 not in num_set: current_num num current_len 1 while current_num 1 in num_set: current_num 1 current_len 1 # 提前终止判断 if len(num_set) - current_num num max_len: break max_len max(max_len, current_len) return max_len3.2 并查集解法这道题还可以用并查集(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): x_root self.find(x) y_root self.find(y) if x_root y_root: return if self.size[x_root] self.size[y_root]: x_root, y_root y_root, x_root self.parent[y_root] x_root self.size[x_root] self.size[y_root] def longestConsecutive(nums): if not nums: return 0 uf UnionFind(nums) num_set set(nums) for num in num_set: if num 1 in num_set: uf.union(num, num 1) return max(uf.size.values())并查集解法的时间复杂度接近O(n)但实际运行效率通常不如哈希集合解法。4. 实际应用与扩展4.1 实际应用场景这个问题看似简单但实际上有很多实际应用用户行为分析分析用户连续登录天数库存管理查找连续的产品序列号时间序列分析识别连续的时间段基因组学寻找DNA序列中的连续模式4.2 问题变种掌握了基础解法后可以尝试解决一些变种问题最长连续递增序列这次要考虑数组中元素的顺序二维最长连续序列扩展到矩阵中的连续路径带权最长连续序列序列中的每个数字有权重求最大权重和4.3 面试技巧在面试中遇到这道题时建议采取以下策略先提出排序解法分析其时间复杂度然后提出哈希集合解法强调O(n)的优势讨论边界条件和优化空间如果时间允许可以提及并查集解法记住要向面试官展示你的思考过程而不仅仅是给出最终答案。解释为什么哈希集合解法更优以及你是如何想到这个解法的。