LeetCode 筆記 - 128. Longest Consecutive Sequence

挑战在無序數列中尋找最長連續子序列，且要求在 O(N) 線性時間內完成。本文分享透過哈希集合快速定位連續區間起點與延伸方向的技巧，是一篇探討如何繞過傳統排序限制、利用空間換取查詢效率的高階演算法心得。

發佈: 2022.07.23
閱讀: 約 1 分鐘
字數: 249

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 128. Longest Consecutive Sequence

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

解題思維

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

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

看過的數字就可以丟掉了

程式碼

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

也許你也會想看看