[Leetcode]128. Longest Consecutive Sequence

題目 : 128. Longest Consecutive Sequence Medium

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.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

1.

numSet : 用set()函數將nums做成集合，去除重複的數字

longest : 紀錄目前最大長度

length : 記錄由num開始算連續數字的長度

line 8 : 先看num是不是連續整數中的最小數，如果是就開始往後找num+1、num+2....

直到找到連續整數的最大長度

line 12 : 跳出迴圈後查看紀錄的length和longest那個最大，用max()回傳最大長度

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        numSet = set(nums)
        longest = 0

        for num in nums :
            if num-1 not in numSet:
                length = 0
                while (num+length) in numSet:
                    length += 1
                longest = max(length,longest)

        return longest