【LeetCode】128. 最长连续序列

0.总结

• 如果想降低时间复杂度，那么可能就要使用大内存（提升空间复杂度）。
• 【一串序列只会有一个起点】

---

1.题目

2.思想

这题还挺难想的。难点在于，如何保证是O(n)的时间复杂度？我们可以设置一个字典用于存储list出现过的数字。当遇到一个数字num的时候，可能其是一串序列的一个数字，也可能是一个单独的数字。【但是我们知道一串序列只会有一个起点】，所以如果该数-1 （num-1）在集合中，那么直接跳过该数，因为它不是本串序列的起点。如果不在集合中，那么赋值res=1。
具体地说：

• （1）定义一个set集合。用于表示当前这个list存在的数
• （2）顺序遍历list中的数，同时判断num-1（ num=nums[i]） 是否在set中，如果在，那么就continue到下一个，否则判断 num+1 是否在set中，更新结果

3.代码

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        a = set(nums)
        res = 0
        for i in range(len(nums)):
            cur_num = nums[i]
            if cur_num - 1 in a: # 如果num-1也存在这个list中，那么就直接continue
                continue
            else: # 开始顺序搜索
                cnt = 0
                while(cur_num in a):
                   cnt+=1
                   cur_num+=1
                res = max(res,cnt)
        return res