# 1. Two Sum
#### Difficulty: Easy, Frequency: High
link: https://leetcode.com/problems/two-sum/

### 1. Brute Force
#### $O(n^2)$ runtime, $O(1)$ space

暴力解，直接用兩層for迴圈檢查所有可能的組合。

##### java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

<font color="#00AB5F ">Accepted</font>
Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum.
Memory Usage: 39.1 MB, less than 63.25% of Java online submissions for Two Sum.

### 2. Two-pass Hash Table
#### $O(n)$ runtime, $O(n)$ space

針對第二層for迴圈改良，用空間換取時間，建立Hash table讓搜尋變成接近constant time。

注意nums裡面可能有重複元素，put會讓後面的覆蓋前面的，由於我們第二個for loop是從前面往後檢查，所以不會發生問題。

##### java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (map.containsKey(key) && i != map.get(key)) {
                return new int[]{i, map.get(key)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

<font color="#00AB5F ">Accepted</font>
Runtime: 3 ms, faster than 45.00% of Java online submissions for Two Sum.
Memory Usage: 38.9 MB, less than 93.50% of Java online submissions for Two Sum.

### 3. One-pass Hash Table
#### $O(n)$ runtime, $O(n)$ space

再簡化過的寫法，只掃過一次array，之後再往前找已經在map內的元素。

##### java

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

##### python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = {}
        for i, n in enumerate(nums):
            x = target - n
            if x in hashtable:
                return [hashtable[x], i]
            hashtable[n] = i

<font color="#00AB5F ">Accepted</font>
Runtime: 44 ms, faster than 87.98% of Python3 online submissions for Two Sum.
Memory Usage: 14.3 MB, less than 94.55% of Python3 online submissions for Two Sum.

###### tags: `leetcode`