Two Sum, 经典中的经典，无需多说。

其实应该条件反射，当需要random查找,并且是根据value查找index, 而且时间是O(1)时: 有映射关系，有random查找，所以是hashtable.

我一开始❌的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int comp = target - nums[i];
            if (map.containsKey(comp) && comp != nums[i]) {
                res[0] = map.get(comp);
                res[1] = i;
            }
            map.put(nums[i], i);
        }
        return res;
    }

❌原因: comp != nums[i]; 虽然题目限定each input would have exactly one solution, 但是实际上满足条件的nums可能就是对应的相同大小的两个数，只不过对应的index不同; 所以进不去if条件，所以res根本就没有赋值

1
2
3
4
5
failed case: 

Input: [3,3], target = 6
Output: [0,0]
Expected: [0,1]

Correct:

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int comp = target - nums[i];
            if (map.containsKey(comp)) {
                res[0] = map.get(comp);
                res[1] = i;
            }
            map.put(nums[i], i);
        }
        return res;
    }

Below are detailed 3 ways in LC Solution section.

  1. Brute Force:

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target - x.

1
2
3
4
5
6
7
8
9
10
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[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Time: O(n^2)
Space: O(1)

  1. Two-pass Hash table

We need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say “near” because if a collision occurred, a look up could degenerate to O(n) time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. In the first iteration, we add each element’s value and its index to the table. Then, in the second iteration we check if each element’s complement (target−nums[i]) exists in the table. Beware that the complement must not be nums[i] itself!

1
2
3
4
5
6
7
8
9
10
11
12
13
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 complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Time: O(n)
Space: O(n)

  1. One-pass Hash Table
1
2
3
4
5
6
7
8
9
10
11
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");
}

Time: O(n)
Space: O(n)