1. 2 Sum

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

1. 2 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 設定為陣列的指標。

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

解題方向

解法一：暴力解

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（這題的正解）

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 時，我們需要知道這個解法；那當然如果是無序排列的陣列，也可以先排序，再開始透過雙指針的方式去找到所有的答案。

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 和 18. 4 Sum 的基礎積木 —— 那兩題要的是「不重複的值組合」，剛好就是這個形態。想直接練這個解法本身，看 167. Two Sum II（陣列已排序，而且題目就要值的位置）。

補充

為什麼這題是 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 —— 在那個題目裡面，題目給我們的是給定四個陣列，從四個陣列中各挑一個數字，其總和要等於給定的目標。整套 n Sum 的應對策略見 2 Sum 面試應對策略。

複雜度

暴力解

時間 $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)$ ，而且保住了原始索引，這是這題唯一不能妥協的條件。