1. 题目解析与核心思路这道题要求我们找出未排序整数数组中最长连续元素序列的长度。关键在于连续的定义——序列中的数字必须是连续整数但不要求在原数组中连续出现。例如对于数组[100,4,200,1,3,2]最长连续序列是[1,2,3,4]长度为4。1.1 暴力解法分析最直观的解法是对于每个数字检查其1、2...是否存在于数组中def longestConsecutive(nums): max_len 0 for num in nums: current_num num current_len 1 while current_num 1 in nums: current_num 1 current_len 1 max_len max(max_len, current_len) return max_len时间复杂度O(n³)因为in操作在Python中平均O(n)而外层还有两层循环。1.2 哈希集优化使用哈希集合存储数字可以将查找时间降到O(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_len时间复杂度降至O(n)因为每个数字最多被访问两次作为序列起点和中间元素。2. 实现细节与边界处理2.1 空数组处理当输入为空数组时应直接返回0if not nums: return 02.2 重复元素处理使用集合自动去重避免重复计算num_set set(nums)2.3 负数和零处理算法天然支持负数和零因为集合查找不依赖数值大小# 测试用例 assert longestConsecutive([0,-1]) 23. 算法优化与变种3.1 并查集解法可以构建数字间的连通关系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) for num in nums: if num 1 in uf.parent: uf.union(num, num 1) return max(uf.size.values())时间复杂度接近O(nα(n))其中α是反阿克曼函数。3.2 动态规划解法使用字典记录边界长度def longestConsecutive(nums): length_map {} max_len 0 for num in nums: if num not in length_map: left length_map.get(num - 1, 0) right length_map.get(num 1, 0) current_len left right 1 length_map[num] current_len length_map[num - left] current_len length_map[num right] current_len max_len max(max_len, current_len) return max_len每个数字只处理一次时间复杂度O(n)。4. 复杂度分析与实测对比4.1 时间复杂度对比方法平均时间复杂度最坏情况暴力法O(n³)O(n³)哈希集O(n)O(n)并查集O(nα(n))O(nα(n))动态规划O(n)O(n)4.2 空间复杂度对比所有方法都需要O(n)额外空间存储中间数据。4.3 LeetCode实测数据在LeetCode判题系统上Python3哈希集解法平均运行时间120ms内存消耗25MB动态规划解法平均运行时间140ms内存消耗28MB并查集解法平均运行时间180ms内存消耗30MB5. 常见错误与调试技巧5.1 典型错误案例错误实现1忘记检查前驱节点# 错误代码会重复计算非起点的序列 for num in num_set: current_num num # 应该先检查num-1是否存在 current_len 1 ...错误实现2错误更新最大值# 错误代码在循环内部错误放置max_len更新 max_len 1 # 应该初始化为0 for num in nums: ... max_len current_len # 应该用max函数比较5.2 调试建议使用简单测试用例验证assert longestConsecutive([]) 0 assert longestConsecutive([1]) 1 assert longestConsecutive([1,3,2]) 3打印中间变量print(fProcessing {num}, current length: {current_len})可视化处理过程[100,4,200,1,3,2] 处理1发现0不存在 → 序列1-2-3-4 处理100发现99不存在 → 序列100 处理4发现3存在 → 跳过 ...6. 实际应用场景6.1 数据库ID连续性检查检查数据库中缺失的ID记录-- 找出缺失的ID WITH consecutive AS ( SELECT id, id - ROW_NUMBER() OVER (ORDER BY id) AS diff FROM table ) SELECT MIN(id), MAX(id), COUNT(*) FROM consecutive GROUP BY diff;6.2 日志时间序列分析找出连续错误日志的时间段error_timestamps [log.timestamp for log in logs if log.status ERROR] max_consecutive longestConsecutive([t.toordinal() for t in error_timestamps])6.3 游戏成就系统统计玩家连续登录天数login_dates [date.toordinal() for date in player.login_history] streak longestConsecutive(login_dates)7. 进阶挑战与扩展7.1 允许k个缺失值变形题允许序列中间最多缺少k个数字求最长序列def longestConsecutiveWithKGaps(nums, k): nums sorted(list(set(nums))) max_len 0 left 0 for right in range(1, len(nums)): gap nums[right] - nums[right-1] - 1 while gap k: left 1 gap nums[right] - nums[left] - (right - left) max_len max(max_len, right - left 1 k) return max_len7.2 二维连续序列矩阵中的最长连续递增路径def longestIncreasingPath(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) memo [[0]*n for _ in range(m)] def dfs(i, j): if not memo[i][j]: val matrix[i][j] memo[i][j] 1 max( dfs(i-1,j) if i0 and matrix[i-1][j]val else 0, dfs(i1,j) if im-1 and matrix[i1][j]val else 0, dfs(i,j-1) if j0 and matrix[i][j-1]val else 0, dfs(i,j1) if jn-1 and matrix[i][j1]val else 0 ) return memo[i][j] return max(dfs(i,j) for i in range(m) for j in range(n))7.3 流式数据处理处理无法完全加载到内存的大数据流class StreamingProcessor: def __init__(self): self.num_set set() self.min_val float(inf) self.max_val -float(inf) def addNum(self, num): self.num_set.add(num) self.min_val min(self.min_val, num) self.max_val max(self.max_val, num) def getLongestConsecutive(self): max_len 0 current_len 0 for num in range(self.min_val, self.max_val 1): if num in self.num_set: current_len 1 max_len max(max_len, current_len) else: current_len 0 return max_len
