【Leetcode 筆記】 128. Longest Consecutive Sequence

題目解釋

給定一個 unsorted 的整數陣列 nums，傳回最長連續序列的長度。

演算法的 time comlexity 必須是 O(n)。

範例

• 輸入: nums = [100, 4, 200, 1, 3, 2]
• 輸出: 4

輸出 4 是因為 1, 2, 3, 4 是最大的連續序列。

最佳解法

首先，我們可以思考「連續」的定義：
當有一個數字 n 時，只要再給一個 n - 1 的數值，我們就可以拿到一個連續的 seq，例如 [0, 1] 等。

=>因此，如果 n - 1 存在於 array 中的話，就代表 n 不是連續 seq 的起點！

所以我們需要將 traverse 的結果寫在某種資料結構內，而這個最理想的資料結構就是 set。

步驟

1. 將 nums 直接轉換為 set
2. 確保我們在連續 seq 的起點 (if (n - 1) not in nums_set)
3. 從起點持續向後滾動並累積 seq_len
4. 最後 return max_seq_len

⚠️ 注意

• Q：為什麼 max_seq_len = max(seq_len, max_seq_len) 這段不可以放在 while 裡？
• A：因為如果我們沒有進到 while 迴圈那 max_seq_len 就不會被更新，例如 nums = [0] 時，我們期待的結果是 1，但是因為寫在裡面所以會回傳錯誤的 0。

程式碼

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

        for n in nums_set:
            if (n - 1) not in nums_set:
                seq_len = 1
                while (n + seq_len) in nums_set:
                    seq_len += 1
                max_seq_len = max(seq_len, max_seq_len)

        return max_seq_len

時間複雜度

O(n)，n 是 nums 的元素個數。

空間複雜度

O(n)。

結語

看起來很簡單，但若沒想清楚的下場就是一直吃 Wrong Answer 🥲。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26