題目描述:給定未排序的整數陣列,找出最長連續整數序列的長度,要求 O(n) 時間複雜度。
解題思路:將所有數字存入 unordered_set。對每個數字 n,只有當 n-1 不在集合中時,n 才是某個連續序列的起點。從起點開始向右延伸(不斷查找 n+1, n+2...),計算序列長度。由於每個數字只作為起點一次,總時間仍為 O(n)。
時間複雜度:O(n) — 每個數字最多被遍歷兩次(作為起點一次,作為序列成員一次)。
空間複雜度:O(n) — 雜湊集合儲存所有元素。
1. Insert all nums into a hash set
2. For each n in set:
a. If (n-1) not in set (n is sequence start):
b. Extend: while (n+1) in set, increment n and length
c. Update longest
3. Return longest排序 O(n log n):排序後遍歷,計算連續段 — 時間複雜度更差。
DP O(n) 但空間 O(max_num):用陣列記錄各值的最長連續序列,適用於有界整數。