167. Two Sum II - Input Array Is Sorted

Two Sum II - Input Array Is Sorted

題目描述： 給定一個已按升序排序的整數陣列 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) — 只使用了兩個指標變數，不需要任何額外的輔助資料結構，空間為常數級別。

二分搜尋法 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) 額外空間，且未利用「已排序」的特性，是較浪費資訊的做法。對於本題，雙指標是最優解。

1. 若陣列未排序，你會選擇哪種方法（雜湊表 O(n) 還是排序後雙指標 O(n log n)）？在什麼條件下各自更有優勢？
2. 如果題目改為找三個數相加等於目標值（3Sum，LeetCode 15），雙指標的思路如何延伸應用？
3. 雙指標法正確性的關鍵在於陣列已排序。請說明：為什麼每次移動指標時，被排除的那一側的所有組合都確實不可能是答案？