【LeetCode】128. Longest continuous sequence

0. summary

• If you want to reduce the time complexity , Then you may need to use large memory （ Increase space complexity ）.
• 【 A sequence has only one starting point 】

---

1. subject

2. thought

This is a difficult question to think about . The difficulty lies in , How to ensure that O(n) Time complexity of ？ We can set up a dictionary to store list Numbers that have appeared . When you come across a number num When , Maybe it's a number in a sequence , It could also be a single number .【 But we know that a sequence has only one starting point 】, So if the number -1 （num-1） In the assembly , Then skip the number , Because it is not the starting point of this sequence . If it's not in the collection , So assignment res=1.
To be specific ：

• （1） Define a set aggregate . Used to indicate the current list Number of existing
• （2） Sequential traversal list The number in , At the same time judge num-1（ num=nums[i]） Whether in set in , If in , then continue To the next , Otherwise, judgment num+1 Whether in set in , Update results

3. Code

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: #  If num-1 There is also this list in , Then directly continue
                continue
            else: #  Start sequential search 
                cnt = 0
                while(cur_num in a):
                   cnt+=1
                   cur_num+=1
                res = max(res,cnt)
        return res