本文深入解析 leetcode 128 题“最长连续序列”中看似 o(n) 实际退化为 o(n²) 的常见写法，指出外层循环遍历原始数组而非去重集合是导致超时的关键原因，并提供可落地的优化方案。
本文深入解析 leetcode 128 题“最长连续序列”中看似 o(n) 实际退化为 o(n²) 的常见写法，指出外层循环遍历原始数组而非去重集合是导致超时的关键原因，并提供可落地的优化方案。
在解决 LeetCode 128 题「最长连续序列」时，许多开发者会写出逻辑正确、理论时间复杂度为 O(n) 的哈希集合解法，却仍遭遇 Time Limit Exceeded（TLE） —— 尤其在含大量重复元素的大规模测试用例中。问题不在于算法思想，而在于一个极易被忽视的实现细节：外层循环的迭代对象选择。
标准 O(n) 解法的核心思路是：
- 将数组转为集合
s，实现 O(1) 查找； - 对每个可能的「连续序列起点」（即
num - 1不在集合中），向右延伸统计长度； - 跳过所有非起点元素，确保每个数字最多被访问 2 次（一次判断是否为起点，一次在某次延伸中被命中），从而保证均摊 O(n)。
但以下写法是典型陷阱：
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
longest_streak = 0
for num in nums: # ⚠️ 危险：遍历原始列表 nums！
if (num - 1) not in s:
current_streak = 1
while (num + 1) in s:
num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak⚠️ 问题根源：for num in nums
若输入为 [1,1,1,...,1]（10⁵ 个重复元素），外层循环将执行 10⁵ 次，每次都要做 if (num - 1) not in s 判断——而该判断本身虽为 O(1)，但总次数不再是 O(n)，而是 O(n × 重复次数)。最坏情况下（全相同元素），时间复杂度退化为 O(n²)，直接触发 TLE。
✅ 正确做法：外层循环必须遍历去重后的集合：
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
s = set(nums) # 去重
longest_streak = 0
for num in s: # ✅ 正确：遍历集合，无重复
if (num - 1) not in s: # 是连续序列起点
current_num = num
current_streak = 1
while (current_num + 1) in s:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak? 关键差异说明：
for num in nums→ 迭代n次（含重复）for num in s→ 迭代≤ n次（实际为唯一元素数，记为m ≤ n）- 内层
while循环对每个起点最多执行len(序列)次，所有起点的延伸总长度 ≤m，故总操作数 ≤2m = O(n)。
此外，关于「为何 O(n log n) 排序解法有时比错误 O(n) 解更快？」：
时间复杂度描述的是渐近增长趋势，而非绝对耗时。排序（如 Timsort）在小规模或部分有序数据上常有极低常数因子和优秀缓存局部性；而错误 O(n) 解因重复扫描，在中等规模（如 10⁴~10⁵）含重复数据时，实际操作数远超 n，导致运行时反而更慢。这也是为什么你的排序解获得 93.93% 分位，而错误 O(n) 解 TLE 的根本原因。
? 总结建议：
- 写 O(n) 哈希解时，外层循环永远基于
set(nums)，而非nums； - 避免复用循环变量（如
num在while中被修改），虽不影响正确性，但降低可读性与调试效率； - 理解「理论复杂度」与「工程性能」的区别：常数因子、内存局部性、输入分布均影响实测表现；
- LeetCode 测试用例常包含极端重复数据，是检验实现鲁棒性的关键场景。
