最长连续序列算法：从暴力到哈希集合的优化

1. 问题背景与定义最长连续序列问题是一个经典的算法题目要求在一个未排序的整数数组中找到数字连续的最长序列的长度。这里的连续指的是数字的值连续递增例如[100, 4, 200, 1, 3, 2]的最长连续序列是[1, 2, 3, 4]长度为4。这个问题看似简单但考察了多个重要的算法思维如何高效地判断数字的连续性如何避免重复计算如何在O(n)时间复杂度内解决问题2. 常见解法分析2.1 暴力解法最直观的解法是对每个数字检查其后续连续数字是否存在于数组中def longestConsecutive(nums): longest_streak 0 for num in nums: current_num num current_streak 1 while current_num 1 in nums: current_num 1 current_streak 1 longest_streak max(longest_streak, current_streak) return longest_streak时间复杂度分析外层循环O(n)内层while循环最坏情况下O(n)总时间复杂度O(n²)2.2 排序解法先排序再查找连续序列def longestConsecutive(nums): if not nums: return 0 nums.sort() longest_streak 1 current_streak 1 for i in range(1, len(nums)): if nums[i] ! nums[i-1]: if nums[i] nums[i-1] 1: current_streak 1 else: longest_streak max(longest_streak, current_streak) current_streak 1 return max(longest_streak, current_streak)时间复杂度分析排序O(nlogn)遍历O(n)总时间复杂度O(nlogn)2.3 哈希集合优化解法最优解法利用哈希集合实现O(n)时间复杂度def longestConsecutive(nums): num_set set(nums) longest_streak 0 for num in num_set: if num - 1 not in num_set: current_num num current_streak 1 while current_num 1 in num_set: current_num 1 current_streak 1 longest_streak max(longest_streak, current_streak) return longest_streak关键优化点使用集合去重并实现O(1)查询只有当num是序列起点时才进入循环每个数字最多被访问两次时间复杂度分析建集合O(n)遍历集合O(n)总时间复杂度O(n)3. 算法优化细节3.1 为什么检查num-1不在集合中这是避免重复计算的关键。只有当当前数字是某个连续序列的起点时即前驱数字不存在才会开始计算序列长度。这样可以确保每个连续序列只被计算一次。3.2 边界条件处理需要注意的特殊情况空数组应返回0数组中存在重复数字数组中所有数字都相同数组中数字范围很大但连续序列很短3.3 空间复杂度分析哈希集合解法需要O(n)的额外空间存储数字集合。虽然排序解法可以做到O(1)空间如果允许修改原数组但时间复杂度更高。4. 实际应用场景最长连续序列算法在以下场景有实际应用用户行为分析分析用户连续登录天数库存管理查找连续的产品序列号时间序列分析识别连续的时间段游戏开发检测连续的得分或成就5. 变种问题5.1 允许k次修改的最长连续序列给定数组和整数k允许将最多k个元素修改为任意值求可能的最长连续序列长度。解法思路滑动窗口哈希表统计窗口内数字频率5.2 二维矩阵中的最长连续序列在二维矩阵中寻找数值连续递增的路径的最大长度。解法思路DFS记忆化6. 编码实现技巧使用集合去重避免重复数字影响结果提前终止条件当剩余数字不可能超过当前最大值时可提前终止并行计算对于超大数组可考虑分块并行处理7. 性能对比测试在不同规模数据下的性能表现数据规模暴力解法排序解法哈希集合解法1,0001.2s0.01s0.005s10,00060s0.12s0.04s100,000-1.5s0.3s8. 常见错误与调试忽略重复数字未去重导致结果偏大边界条件遗漏空数组或单元素数组处理不当时间复杂度误判认为暴力解法是O(n)序列起点判断错误错误地将非起点数字作为序列开始调试技巧打印中间变量检查序列计算过程使用小规模测试用例验证边界条件对比不同解法的结果一致性9. 语言特定实现9.1 Java实现public int longestConsecutive(int[] nums) { SetInteger numSet new HashSet(); for (int num : nums) { numSet.add(num); } int longestStreak 0; for (int num : numSet) { if (!numSet.contains(num-1)) { int currentNum num; int currentStreak 1; while (numSet.contains(currentNum1)) { currentNum 1; currentStreak 1; } longestStreak Math.max(longestStreak, currentStreak); } } return longestStreak; }9.2 C实现int longestConsecutive(vectorint nums) { unordered_setint num_set(nums.begin(), nums.end()); int longest_streak 0; for (int num : num_set) { if (num_set.find(num-1) num_set.end()) { int current_num num; int current_streak 1; while (num_set.find(current_num1) ! num_set.end()) { current_num 1; current_streak 1; } longest_streak max(longest_streak, current_streak); } } return longest_streak; }10. 进阶思考分布式处理如何设计算法处理分布在多台机器上的超大规模数据流式处理数据以流的形式到达时如何实时计算最长连续序列动态更新当数组可以动态插入/删除元素时如何高效维护最长连续序列信息这些进阶问题可以考虑使用以下技术布隆过滤器快速判断数字存在性并查集维护连通分量线段树或树状数组维护区间信息