---
title: "167. Two Sum II - Input array is sorted"
url: "https://laigary.com/interview/coding/167-two-sum-ii-input-array-is-sorted"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-25"
tags: ["Two Pointers", "Classic", "Binary Search"]
---

# 167. Two Sum II - Input array is sorted

[167\. Two Sum II - Input array is sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)

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

## 思路

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

這題是理解「**為什麼對撞指針是對的**」最乾淨的範例，值得把論證講清楚，因為同一套推理會在 [11](/interview/coding/11-container-with-most-water)、[42](/interview/coding/42-trapping-rain-water)、[15](/interview/coding/15-3-sum) 反覆出現。

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

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

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

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

## 解題方向

```python
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]` 是很自然的想法：

```python
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 模板](/interview/coding/binary-search-template)。

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

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

## 複雜度

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

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

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