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

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

128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements 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)。