classSolution:deflongestConsecutive(self,nums:List[int])-int:stset(nums)# 把 nums 转成哈希集合ans0forxinst:# 遍历哈希集合ifx-1inst:# 如果 x 不是序列的起点直接跳过continue# x 是序列的起点yx1whileyinst:# 不断查找下一个数是否在哈希集合中y1# 循环结束后y-1 是最后一个在哈希集合中的数ansmax(ans,y-x)# 从 x 到 y-1 一共 y-x 个数returnans首先本题是不能排序的因为排序的时间复杂度是 O(nlogn)不符合题目 O(n) 的要求。核心思路对于 nums 中的元素 x以 x 为起点不断查找下一个数 x1,x2,x3,… 是否在 nums 中同时统计连续序列的长度。为了做到 O(n) 时间复杂度需要两个关键优化把 nums 中的数都放入一个哈希集合中这样可以 O(1) 判断数字是否在 nums 中。如果 x−1 在哈希集合中则不以 x 为起点。为什么因为以 x−1 为起点计算出的序列长度一定比以 x 为起点计算出的序列长度要长这样可以避免大量重复计算。比如 nums[3,2,4,5]从 3 开始我们可以找到 3,4,5 这个连续序列而从 2 开始我们可以找到 2,3,4,5 这个连续序列一定比从 3 开始的序列更长。⚠注意遍历元素的时候要遍历哈希集合而不是 nums如果 nums[1,1,1,…,1,2,3,4,5,…]前一半都是 1遍历 nums 的做法会导致每个 1 都跑一个 O(n) 的循环总的循环次数是 O(n2)会超时。时间复杂度O(n)其中 n 是 nums 的长度。在二重循环中每个元素至多遍历两次在外层循环中遍历一次在内层循环中遍历一次。所以二重循环的时间复杂度是 O(n) 的。比如 nums[1,2,3,4]其中 2,3,4 不会进入内层循环只有 1 会进入内层循环。空间复杂度O(m)。其中 m 是 nums 中的不同元素个数。
