題目描述:
給定一個已按升序排序的整數陣列 numbers(1-indexed),找出兩個數字使其相加等於目標值 target,回傳它們的索引(以 1 為起始)。題目保證恰好存在一組解,且不能使用同一個元素兩次。
解題思路: 由於陣列已排序,使用**雙指標(Two Pointers)**可達到最優效率,無需額外空間。
設置兩個指標:
left 指向陣列開頭(最小值)。right 指向陣列末尾(最大值)。在每一步計算 sum = numbers[left] + numbers[right]:
sum == target:找到答案,回傳 {left + 1, right + 1}(轉換為 1-indexed)。sum < target:總和太小,需要更大的數,將 left 向右移動(left++)。sum > target:總和太大,需要更小的數,將 right 向左移動(right--)。因為題目保證恰好有一組解,指標最終必然會相遇於正確答案,不需要額外的邊界判斷。
此方法充分利用了「已排序」這一前提條件,每次移動指標都能排除一個不可能的候選值,因此整個搜尋過程是線性的。
時間複雜度:O(n) — 兩個指標從兩端向中間靠攏,每次迴圈至少移動一個指標,最多執行 n-1 次迭代,其中 n 為陣列長度。
空間複雜度:O(1) — 只使用了兩個指標變數,不需要任何額外的輔助資料結構,空間為常數級別。
1. Set left = 0, right = len(numbers) - 1. 2. While left < right: a. Compute sum = numbers[left] + numbers[right]. b. If sum == target: return [left + 1, right + 1]. c. If sum < target: increment left (need a larger value). d. If sum > target: decrement right (need a smaller value). 3. Return empty (guaranteed not to reach here).
二分搜尋法 O(n log n):對每個元素 numbers[i],在 i+1 到末尾的子陣列中用二分搜尋找 target - numbers[i]。時間複雜度為 O(n log n),空間 O(1),但效率不如雙指標法。
雜湊表法 O(n):使用雜湊表記錄每個值的索引,對每個元素查找 target - numbers[i] 是否已存在於表中。時間 O(n),但需要 O(n) 額外空間,且未利用「已排序」的特性,是較浪費資訊的做法。對於本題,雙指標是最優解。