最長連續序列 (Longest Consecutive Sequence) - LeetCode 題解
題目描述
給定一個未排序的整數數組 nums，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。要求設計并實現時間復雜度為 O(n) 的算法解決此問題。
示例 1：
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數字連續序列是 [1, 2, 3, 4]。它的長度為 4。
示例 2：
輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9
解釋：最長數字連續序列是 [0,1,2,3,4,5,6,7,8]。它的長度為 9。
示例 3：
輸入：nums = [1,0,1,2]
輸出：3
解釋：最長數字連續序列是 [0,1,2]。它的長度為 3。
解題思路
方法一：哈希集合（推薦）
-
哈希集合預處理：
- 將所有數字存入哈希集合中，實現O(1)時間復雜度的查找
- 去重處理，避免重復數字的影響
-
尋找連續序列：
- 遍歷數組中的每個數字
- 對于每個數字，檢查它是否是某個連續序列的起點（即num-1不在集合中）
- 如果是起點，則向后查找連續的數字，計算當前連續序列的長度
- 更新最長連續序列的長度
-
復雜度分析：
- 時間復雜度：O(n)，每個數字最多被訪問兩次（一次在哈希集合中，一次在連續序列查找中）
- 空間復雜度：O(n)，用于存儲哈希集合
方法二：排序法（不滿足O(n)要求）
-
排序數組：
- 先對數組進行排序
- 然后遍歷排序后的數組，尋找最長連續序列
-
缺點：
- 時間復雜度為O(n log n)，不滿足題目要求
- 僅作為對比思路提及
Go 代碼實現
func longestConsecutive(nums []int) int {if len(nums) == 0 {return 0}// 創建哈希集合存儲所有數字numSet := make(map[int]bool)for _, num := range nums {numSet[num] = true}longestStreak := 0// 遍歷哈希集合中的每個數字for num := range numSet {// 檢查當前數字是否是某個連續序列的起點if !numSet[num-1] {currentNum := numcurrentStreak := 1// 向后查找連續的數字for numSet[currentNum+1] {currentNum++currentStreak++}// 更新最長連續序列長度if currentStreak > longestStreak {longestStreak = currentStreak}}}return longestStreak
}func main() {// 示例測試nums1 := []int{100, 4, 200, 1, 3, 2}result1 := longestConsecutive(nums1)fmt.Println("Longest consecutive sequence length:", result1) // 輸出: 4nums2 := []int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}result2 := longestConsecutive(nums2)fmt.Println("Longest consecutive sequence length:", result2) // 輸出: 9nums3 := []int{1, 0, 1, 2}result3 := longestConsecutive(nums3)fmt.Println("Longest consecutive sequence length:", result3) // 輸出: 3
}
測試用例
func TestLongestConsecutive(t *testing.T) {tests := []struct {input []intwant int}{{[]int{100, 4, 200, 1, 3, 2}, 4},{[]int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}, 9},{[]int{1, 0, 1, 2}, 3},{[]int{}, 0},{[]int{1}, 1},{[]int{1, 3, 5, 7, 9}, 1},{[]int{1, 2, 3, 4, 5}, 5},{[]int{5, 4, 3, 2, 1}, 5},}for _, tt := range tests {got := longestConsecutive(tt.input)if got != tt.want {t.Errorf("longestConsecutive(%v) = %d, want %d", tt.input, got, tt.want)}}
}
復雜度分析
-
時間復雜度：O(n)
- 創建哈希集合：O(n)
- 遍歷哈希集合：每個數字最多被訪問兩次（一次在哈希集合中，一次在連續序列查找中）
- 總體時間復雜度為線性
-
空間復雜度：O(n)
- 需要額外的哈希集合存儲所有數字
優化思路
-
并行處理：
- 對于大規模數據，可以考慮將數組分割后并行處理
- 需要處理邊界條件和合并結果
-
內存優化：
- 如果數字范圍有限，可以使用位圖代替哈希集合
- 減少內存使用，提高緩存命中率
-
流式處理：
- 對于無法一次性加載到內存的超大數據集
- 可以使用外部排序和分段處理技術
總結
這道題考察了對哈希數據結構的靈活運用，關鍵在于如何高效地判斷連續序列的起點和計算序列長度。通過使用哈希集合，我們可以在O(n)時間復雜度內解決問題，這比排序法更高效。掌握這種利用空間換時間的思路對解決類似問題很有幫助。
擴展思考
- 如果要求返回最長的連續序列本身而不僅僅是長度，該如何修改代碼？
- 如何修改算法以處理包含重復數字的情況（雖然當前解法已經處理了）？
- 如果數字范圍非常大但稀疏，如何進一步優化空間復雜度？
