企业官网建设流程全解析

LeetCode 128. 最长连续序列

思路

题目要求在O(n)时间复杂度内找到最长连续序列，因此不能直接排序，因为排序的时间复杂度为O(n log n)。

使用set（哈希集合）保存所有数字：

st=set(nums)

这样可以在平均O(1)时间内判断某个数字是否存在。

核心思路

对于当前数字x：

• 如果x - 1存在，说明x不是连续序列的起点，直接跳过。
• 如果x - 1不存在，说明x是起点，从x + 1开始不断向后查找。

例如：

nums = [100, 4, 200, 1, 3, 2] 连续序列： 1 → 2 → 3 → 4 长度 = 4

其中只有1是起点，因为：

0 不存在 → 1 是起点 1 存在 → 2 不是起点 2 存在 → 3 不是起点 3 存在 → 4 不是起点

这样可以避免从2、3、4再次重复查找。

代码

classSolution:deflongestConsecutive(self,nums:list[int])->int:st=set(nums)ans=0forxinst:# x 不是连续序列的起点ifx-1inst:continue# x 是起点，向后查找y=x+1whileyinst:y+=1ans=max(ans,y-x)returnans

为什么for + while还是 O(n)？

虽然代码中存在for和while，但不会对每个数字都完整向后查找。

例如：

1 → 2 → 3 → 4

只有1会执行完整的：

1 → 2 → 3 → 4

而2、3、4因为前一个数字存在，会直接continue。

因此每条连续序列只会被完整扫描一次，总时间复杂度仍然是：

O(n)

空间复杂度：

O(n)

补充：为什么排序是 O(n log n)？

如果先排序再遍历：

排序：O(n log n) 遍历：O(n) 总复杂度： O(n log n) + O(n) = O(n log n)

log₂n可以理解为：

一个数连续除以 2，需要多少次才能变成 1。

例如：

8 → 4 → 2 → 1 一共除 3 次

因为：

2³ = 8

所以：

log₂8 = 3

同理：

16 → 8 → 4 → 2 → 1 log₂16 = 4

因此，当一个算法每次都把问题规模缩小一半时，通常会出现O(log n)。

总结

将数组放入set，只从连续序列的起点x开始向后查找。判断起点的方法是检查x - 1是否存在，从而避免重复计算，将时间复杂度降低到O(n)。