Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Thinking

遇到这种2 sum，3 sum，n sum的题目，无外乎就是两种思路
1. 用一个HashMap，用来保存查找过的数字
2. 双指针法（适用于数组有序的情况）

因为这道题需要返回数组的index，所以我们不能使用第二种解法，因为排序之后的数组index都变了。所以这里我们采用第一种解法。

Solution

遍历数组，用一个HashMap保存已经访问过的数字。对于每个新的数字v，查看HashMap中是否存在target - v。如果是则直接返回他们的index

1
2
3
4
5
6
7
8
9
10
11
12

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> valToIdx = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (valToIdx.containsKey(target - nums[i])) {
            return new int[]{valToIdx.get(target - nums[i]), i};
        }
        
        valToIdx.put(nums[i], i);
    }
    
    throw new IllegalStateException("Should not reach here");
}

时间复杂度：O(N)
空间复杂度：O(N)
N是数组的大小