[Python][Leetcode] 練習題目Longest Consecutive Sequence

最近感覺有點瓶頸的感覺，來練習Leetcode並做筆記記錄下來。

128. Longest Consecutive 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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

題目：Longest Consecutive Sequence，要求你在 O(n) 時間內找到 最長的連續序列長度。

✅ 題目關鍵：

• 連續數列（consecutive） 不要求順序，但數字之間是連著的（例如 [100, 4, 200, 1, 3, 2] → 最長連續序列為 [1, 2, 3, 4]，長度是 4）。
• 時間複雜度限制 O(n) ⇒ 暗示 不能排序（排序是 O(n log n)）。

程式碼

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 將數字放入 set 去除重複，加速查找
        nums_set = set(nums)
        max_length = 0

        # 遍歷每個數字，找出連續序列的起點
        for num in nums_set:
            # 只有當 num - 1 不在 set 中，才是序列的起點
            if num - 1 not in nums_set:
                current_num = num
                length = 1

                # 往上尋找連續的數字
                while current_num + 1 in nums_set:
                    current_num += 1
                    length += 1

                # 更新目前找到的最長長度
                max_length = max(max_length, length)

        return max_length

🧠 解題思路（O(n) 方法）：

使用 HashSet（集合）來加速查找。核心思想如下：

1. 把所有數字放入 set。
2. 對每個數 num，只在「它是連續序列起點」時開始往上找（也就是當 num - 1 不在 set 中）。
3. 從這個起點 current_num不斷加 1，直到 current_num+ k 不在 set 中為止，記錄長度。
4. 持續更新最大長度max_length。

這樣，每個元素最多只會處理一次，因此是 O(n)。