LeetCode 筆記 - 128. Longest Consecutive Sequence

Posted on

題目在此 128. Longest Consecutive Sequence

給一個數列，請計算出最長連續子序列的長度
請實作出 time complexity O(n) 的演算法

解題思維

我覺得這題非常有趣，當初也是撞牆了不少次

這題關鍵是每個數字判斷一次就好，所以當我們看到一個數字，就可以左邊右邊延伸看看
看看可以延伸到多長

看過的數字就可以丟掉了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        if (size := len(nums)) <= 1:
            return size
        
        nums = set(nums)
        
        result = 0
        while nums:
            n = nums.pop()
            
            left_count = 1
            while n - left_count in nums:
                nums.remove(n - left_count)
                left_count += 1
                
            right_count = 1
            while n + right_count in nums:
                nums.remove(n + right_count)
                right_count += 1
            
            result = max(result, left_count + right_count - 1)
        
        return result

相關文章