---
title: "1. 2 Sum"
url: "https://laigary.com/interview/coding/1-2-sum"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-25"
tags: ["Two Pointers", "Hash Table", "Classic"]
---

# 1. 2 Sum

[1\. 2 Sum](https://leetcode.com/problems/two-sum/)

給一個**未排序**的陣列和 `target`，找出兩個數字加起來等於 `target`，回傳它們在**原陣列**的索引。

## 思路

Two sum 最簡單的就是用窮舉法把所有的組合都列出來，時間複雜度為 $O(n^2)$，而且一直到 n Sum 都可以使用這樣的方式來做。當然就是時間複雜度太高了。

要優化就得先看清楚**暴力解在重複做什麼**：對每個 `i`，內層迴圈把右邊整片掃過去，只為了找一個特定的值 `target - nums[i]`。這是一個**查詢**動作 —— 而「快速查詢某個值在不在」正是 hash table 的本業。

於是關鍵的轉念是：不要問「我右邊有沒有那個補數」，而要問「**我左邊有沒有看過那個補數**」。這兩個問法找到的答案完全一樣（任何一組答案都有一個較後面的元素），但後者只需要一趟遍歷。

`Hash Table` 的原理很簡單，那就是我們在遍歷陣列中的每個元素的時候，將目標減去當下的值得到的餘值，**「回」**去 `Hash Table` 裡面找，看看這個餘值有沒有在裡面。如果有的話，代表在迭代到當下這個數字「之前」，有一個數字就是這個餘值，而這個餘值的座標就是我們要的第一個座標。

為什麼會在之前呢？因為上面這個步驟，我們透過餘值在 `Hash Table` 找的時候，如果沒有餘值，我們就把當下的數字做為 `key` 放進去 `Hash Table` 裡面，並將其 `value` 設定為陣列的指標。

儘管是簡單的題目，但我在第一次刷題的時候，記得想出這個方法的時候心裡還是有一種「哇！原來這就是刷題的感覺啊，所有的東西我都會，都很常用，但是第一次要把他們用在一起的時候，是沒辦法瞬間做到的」。

## 解題方向

### 解法一：暴力解

```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return [-1, -1]
```

一定要能先寫出這個 —— 它是後面所有優化的起點，而且 n Sum 的暴力解都是同一個形狀。

### 解法二：Hash Table（這題的正解）

```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        table = {}
        for i, num in enumerate(nums):
            if target - num in table:
                return [table[target - num], i]
            table[num] = i
        return [-1, -1]
```

`table[num] = i` 一定要放在**查詢之後**，否則 `target == num * 2` 的時候會把自己當成配對（例如 `nums = [3, 3], target = 6` 應該回 `[0, 1]`，但先寫入就會回 `[0, 0]`）。

最後那行 `return [-1, -1]` 在 LeetCode 上走不到（題目保證有解），但面試時留著才完整。

### 解法三：排序 + 對撞指針（**不能直接用在這題**）

如果題目的陣列是有序排列的陣列，也可以使用雙指針來找到。這個方法很重要是因為在未來要拓展到 n Sum 時，我們需要知道這個解法；那當然如果是無序排列的陣列，也可以先排序，再開始透過雙指針的方式去找到所有的答案。

```python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[List[int]]:
        numbers.sort()      # 注意：這一步就毀掉了原始索引
        res = []
        left, right = 0, len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            leftVal, rightVal = numbers[left], numbers[right]
            if total < target:
                left += 1
            elif total > target:
                right -= 1
            else:
                res.append([leftVal, rightVal])
                # 跳過重複值，避免同一組答案被算兩次
                while left < right and numbers[left] == leftVal:
                    left += 1
                while left < right and numbers[right] == rightVal:
                    right -= 1
        return res
```

**這份程式碼回傳的是「值」，不是索引** —— 因為 `sort()` 之後索引已經對不回原陣列了。而 1. 2 Sum 要的正是原陣列的索引，所以**這個解法在這題是不能用的**。

那為什麼還要寫？因為它是 [15. 3 Sum](/interview/coding/15-3-sum) 和 [18. 4 Sum](/interview/coding/18-4-sum) 的基礎積木 —— 那兩題要的是「不重複的值組合」，剛好就是這個形態。想直接練這個解法本身，看 [167. Two Sum II](/interview/coding/167-two-sum-ii-input-array-is-sorted)（陣列已排序，而且題目就要值的位置）。

## 補充

**為什麼這題是 hash table 而不是雙指針**，值得記清楚，因為這是「題目要什麼」決定解法的典型例子：

| | 1. 2 Sum | 167. Two Sum II |
|---|---|---|
| 陣列 | 未排序 | 已排序 |
| 要回傳 | **原陣列的索引** | 位置（1-indexed） |
| 能不能排序 | **不能**（會毀掉索引） | 不需要 |
| 解法 | Hash Table，$O(n)$ 時間 $O(n)$ 空間 | 對撞指針，$O(n)$ 時間 $O(1)$ 空間 |

`Hash Table` 在 LeetCode 的很多題目裡面扮演著很重要的角色，因為它可以很高效的讓我們儲存值並記錄很多的資訊，而且可以快速的找到我們要的答案。這個方法好在我們不用重新排序陣列，又或是題目如果限制我們對陣列的排序的時候可以用。

**往下延伸**：這個解法可以拿去挑戰 [454. 4 Sum II](/interview/coding/454-4-sum-ii) —— 在那個題目裡面，題目給我們的是給定四個陣列，從四個陣列中各挑一個數字，其總和要等於給定的目標。整套 n Sum 的應對策略見 [2 Sum 面試應對策略](/interview/coding/2-sum-in-interview)。

## 複雜度

**暴力解**
- 時間 $O(n^2)$ — 每個 `i` 都掃一遍右邊
- 空間 $O(1)$

**Hash Table**
- 時間 $O(n)$ — 一趟遍歷，每次查詢與寫入都是均攤 $O(1)$
- 空間 $O(n)$ — 最壞情況整個陣列都進了 table

**排序 + 對撞指針**
- 時間 $O(n \log n)$ — 排序主導，對撞本身只要 $O(n)$
- 空間 $O(1)$ 或 $O(n)$ — 取決於排序是否原地

其中 $n$ 是陣列長度。這題的正解是 hash table：它用 $O(n)$ 空間換掉了排序的 $O(n \log n)$，而且**保住了原始索引**，這是這題唯一不能妥協的條件。