128. Longest Consecutive Sequence

Question: Longest Consecutive Sequence

Solution

要找連續的數字，第一個是想到用 hash map [0, 0, 0, 0......, 0, 0, 0]

但如題目所述，如果數字範圍很大的話，這個 hash map 就會很長，會需要很多記憶體空間做儲存，因此不可行

分析題目：

nums = [100,4,200,1,3,2]

用看的可以很快分成 3 個連續數字串

[1, 2, 3, 4] [100] [200]

可以發現三個數字串都有一個開頭，所以首先我們要找出數字串的開頭，再去一個一個找它後面還有沒有人。

1. 找 start number：找的方式是 “check no left”，確定 number list 中沒有它前一個數字！

   要找東西有沒有存在，用 set: 先把 numbers 存成 set data structure

   

2. 是 start number：往後找他下一個數字，還有，就繼續

   1 → 2 → 3 →4 → 沒了！

   長度 4

   把長度記起來，如果有比它更長的，就替換掉

3. 不是 start number：跳過

class Solution:

def longestConsecutive(self, nums: List[int]) -> int:

max_length = 0

nums = set(nums)

for num in nums:

if num - 1 not in nums:

length = 0

while num + length in nums:

length += 1

max_length = max(max_length, length)

return max_length

Time Complexity: O(n)

Space Complexity: O(n)

Video Solution