[Leetcode]128: Longest Consecutive Sequence

Link : https://leetcode.com/problems/longest-consecutive-sequence/

Problem :
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

圖來自leetcode

Thoughts :
1. 先把 nums 放進去 set中，排除重複的數字。
2. 跑 nums迴圈，假設 nums-1 數字有在 set 中，那 nums 就不能當開頭。
3. 如果 nums-1沒有在 set 中，那就可以當開頭，計算值為1，如果 nums+1有在 set中，計算值+1，num+1。
4. 回傳最大的 curr值

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # result
        res = 0
        # 轉成set存，拿掉重複的數字
        nums_set = set(nums)
        # go over the array = nums
        for num in nums:
            # 如果 nums-1 存在 nums_set中，num不能作為起始點，跳過
            if num-1 not in nums_set:
                # 沒有在nums_set中，就可以開始計算長度
                curr = 1
                # 假設 nums+1有在nums_set中
                while num+1 in nums_set:
                    # num +1，長度cur +1
                    num += 1
                    curr += 1
                # 檢查有沒有比之前的result還要大
                res = max(res,curr)
        return res