167. Two Sum II - Input array is sorted

──────────────────────────────────────────────────────────────────────

給一個已排序的陣列和一個 target，找出和等於 target 的那一組數字，回傳它們的位置（1-indexed）。題目保證恰好有一組解，而且同一個元素不能用兩次。

思路

如果已經排序好了，可以直接用 2 Sum 雙指針的方法：左右各一個指針，看兩者的和比 target 大還是小，往中間收。

這題是理解「為什麼對撞指針是對的」最乾淨的範例，值得把論證講清楚，因為同一套推理會在 11、42、15 反覆出現。

假設現在 numbers[left] + numbers[right] < target：

因為陣列已排序，right 是 left 目前能配到的最大夥伴
連最大的夥伴都湊不到 target，那 left 跟任何更小的夥伴只會更小
所以 left 永遠不可能是答案的一部分，可以安心淘汰

> target 時完全對稱：left 是 right 能配到的最小夥伴，連最小的都太大，所以 right 出局。

關鍵是每一步都永久排除掉一個元素，所以最多走 n 步就結束。這也是為什麼不需要回頭、不需要額外空間。

解題方向

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total < target:
                left += 1
            elif total > target:
                right -= 1

        return [-1, -1]

兩個細節：

回傳的是 1-indexed 的位置，所以是 [left + 1, right + 1]。這是這題最常見的粗心錯 —— 邏輯全對但答案錯，而且很難一眼看出來。
迴圈是 left < right 而不是 <=，因為同一個元素不能用兩次。
最後那行 return [-1, -1] 在 LeetCode 上其實走不到（題目保證有解），但留著是好習慣：面試時如果題目沒保證有解，這就是正確的出口。

補充

用二分搜尋也能解。 既然陣列已排序，對每個 i 去二分找 target - numbers[i] 是很自然的想法：

from bisect import bisect_left

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            need = target - numbers[i]
            j = bisect_left(numbers, need, i + 1)   # 從 i+1 開始找，避免用到自己
            if j < len(numbers) and numbers[j] == need:
                return [i + 1, j + 1]
        return [-1, -1]

這是對的，但慢一個 log： $O (n \log n)$ 對上對撞指針的 $O (n)$ 。差別在於二分搜尋每次都從頭搜一遍，而對撞指針每一步都帶著上一步的結論繼續走。

面試時這個對比是好素材：先說「排序好了，我可以對每個元素二分找補數， $O (n \log n)$ 」，再說「不過用對撞指針可以做到 $O (n)$ ，因為每一步都能永久淘汰一個元素」。手寫二分的邊界寫法見 Binary Search 模板。

和 1. 2 Sum 的差別就是「有沒有排序」。 那題沒排序，所以只能用 hash table 記補數， $O (n)$ 時間但要 $O (n)$ 空間。167 用「已排序」這個條件換掉了那個空間 —— 和 26. Remove Duplicates from Sorted Array 完全是同一個道理：題目給了 sorted，就要想它能換到什麼。

同一家族的其他變形：15. 3 Sum（固定一個數，剩下的區間用對撞指針）、653. Two Sum IV - Input is a BST（中序遍歷 BST 就得到排序陣列，於是又回到這題）。整套面試應對策略見 2 Sum 面試應對策略，模板見 Two Pointers 模板。

複雜度

對撞指針

時間 $O (n)$ — 每一步淘汰一個元素，兩個指針合計走完陣列一次
空間 $O (1)$ — 只有兩個索引

逐項二分搜尋

時間 $O (n \log n)$ — 每個元素各做一次 $O (\log n)$ 的搜尋
空間 $O (1)$ — bisect 不配置額外空間

其中 $n$ 是陣列長度。兩者空間相同，所以沒有理由選二分搜尋 —— 它的價值只在於「沒想到對撞指針時的保底解法」。