題目描述:給定一個已排序且不含重複元素的整數陣列 nums,要求輸出能夠覆蓋所有數字的最小區間列表。若某個區間只包含單一數字 a,格式為 "a";若包含連續數字 a 到 b(a < b),格式為 "a->b"。
解題思路:使用雙指標的方式掃描陣列。對每個新區間,令 start = i,接著向右移動 j,只要 nums[j] + 1 == nums[j+1](即連續),就持續擴展。當連續性中斷時,記錄區間 [start, j]:若 start == j 則輸出單一數字,否則輸出 nums[start] + "->" + nums[j]。最後將 i 移至 j + 1 開始下一個區間。整個過程僅需一次線性掃描。
時間複雜度:O(n) — 每個元素只被訪問一次,內外兩層迴圈合計剛好走完整個陣列,因此是線性時間。
空間複雜度:O(1) — 不計輸出結果本身,額外使用的變數只有幾個指標和字串拼接的暫存空間,屬於常數額外空間。
1. Initialize an empty result list and index i = 0. 2. While i < n: a. Set start = i. b. While i + 1 < n and nums[i] + 1 == nums[i+1]: increment i. c. If start == i: append to_string(nums[start]) to result. d. Else: append to_string(nums[start]) + "->" + to_string(nums[i]) to result. e. Increment i. 3. Return result.
方法一:逐元素比較(Element-by-Element) 每次與前一個元素比較,決定是要開啟新區間還是延伸現有區間。使用一個變數記錄當前區間的起始值,遍歷到斷點或末尾時再輸出。邏輯上與雙指標相同,但程式結構略有不同。時間複雜度 O(n),空間複雜度 O(1)。
方法二:使用 stringstream 拼接
在輸出格式化時改用 stringstream 或 ostringstream,避免多次字串拼接的潛在開銷(雖然在此題資料量下影響不大)。核心邏輯不變,時間複雜度 O(n),空間複雜度 O(1)。適合在面試中展示對 C++ 字串處理的熟悉度。
["0->2", "4", "6->9"]),還原出原始的整數陣列,你會如何實作?