最长连续序列算法：从暴力到哈希集合的优化-平芜编程栈

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,000	1.2s	0.01s	0.005s
10,000	>60s	0.12s	0.04s
100,000	-	1.5s	0.3s

8. 常见错误与调试

忽略重复数字：未去重导致结果偏大
边界条件遗漏：空数组或单元素数组处理不当
时间复杂度误判：认为暴力解法是O(n)
序列起点判断错误：错误地将非起点数字作为序列开始

调试技巧：

打印中间变量检查序列计算过程
使用小规模测试用例验证边界条件
对比不同解法的结果一致性

9. 语言特定实现

9.1 Java实现

public int longestConsecutive(int[] nums) { Set<Integer> 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(currentNum+1)) { currentNum += 1; currentStreak += 1; } longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; }

9.2 C++实现

int longestConsecutive(vector<int>& nums) { unordered_set<int> 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_num+1) != num_set.end()) { current_num += 1; current_streak += 1; } longest_streak = max(longest_streak, current_streak); } } return longest_streak; }