LeetCode 128. 最长连续序列思路题目要求在O(n)时间复杂度内找到最长连续序列因此不能直接排序因为排序的时间复杂度为O(n log n)。使用set哈希集合保存所有数字stset(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:stset(nums)ans0forxinst:# x 不是连续序列的起点ifx-1inst:continue# x 是起点向后查找yx1whileyinst:y1ansmax(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)。