128. Longest Consecutive Sequence

Medium

Description

給定未排序的整數陣列 nums，找出最長連續序列的長度（元素值連續，如 1,2,3,4）。演算法必須在 O(n) 時間內完成。

Example:

Input: nums = [100,4,200,1,3,2] Output: 4 （最長連續序列為 [1,2,3,4]）

Intuition#

核心思路：用 HashSet 實現 O(1) 查找，只從「序列起點」開始往後數——起點的判斷條件是 num - 1 不在 Set 中。

排序可以解但是 O(n log n)，不符合要求
關鍵觀察：如果 num - 1 存在於陣列中，那 num 不是某個連續序列的起點
只有當 num 是起點時，才開始往後計數 num+1, num+2, ...，每個元素最多被訪問兩次

Approaches#

1: Sorting#

概念: 排序後線性掃描，跳過重複元素，遇到非連續就重置計數
時間複雜度: O(n log n) - 排序主導
空間複雜度: O(1) - 原地排序（或 O(n) 取決於排序實作）

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        nums.sort()

        var longest = 1
        var current = 1

        for (i in 1 until nums.size) {
            if (nums[i] == nums[i - 1]) continue  // 跳過重複
            if (nums[i] == nums[i - 1] + 1) {
                current++
            } else {
                current = 1
            }
            longest = maxOf(longest, current)
        }
        return longest
    }
}

⭐2: HashSet with Sequence Start Detection#

概念: 將所有元素放入 HashSet，遍歷時只對「序列起點」（num - 1 不在 Set 中）開始計數
時間複雜度: O(n) - 建立 Set 為 O(n)，每個元素最多被內層 while 訪問一次，總計 O(n)
空間複雜度: O(n) - HashSet 儲存所有元素

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        val numSet = HashSet<Int>(nums.toSet())
        var longest = 0

        for (num in numSet) {
            // 只有序列起點才開始計數
            if (num - 1 !in numSet) {
                var current = num
                var length = 1

                while (current + 1 in numSet) {
                    current++
                    length++
                }

                longest = maxOf(longest, length)
            }
        }

        return longest
    }
}

時間複雜度分析：雖然有巢狀迴圈（for + while），但每個元素最多作為起點被計數一次，且在 while 中也只被訪問一次。整體每個元素最多被訪問兩次，所以是 O(n) 而非 O(n^2)。

🔑 Takeaways#

Pattern: 序列/區間偵測 -> HashSet + 起點判斷，避免重複計算
關鍵技巧: 「只從起點開始」的策略確保了線性時間。面試時需要能清楚解釋為什麼巢狀迴圈的整體複雜度仍是 O(n)（amortized analysis）