Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

Notice

You may assume that each input would have exactly one solution

Example

numbers=[2, 7, 11, 15], target=9
return [1, 2]

Challenge

Either of the following solutions are acceptable:

O(n) Space, O(nlogn) Time
O(n) Space, O(n) Time

Note

Brute Force就不说了，使用HashMap的解法思路如下：
建立HashMap<Integer, Integer>，key对应该元素的值与target之差，value对应该元素的index。
然后，循环，对每个元素numbers[i]计算该值与target之差，放入map里，map.put(target-numbers[i], i)。
如果map中包含等于该元素值的key值，那么说明这个元素numbers[i]正是map中包含的key对应的差值diff(=target-numbers[map.get(numbers[i])])。那么，返回map中对应元素的index+1放入res[0]，然后将i+1放入res[1]。返回二元数组res，即为两个所求加数的index序列。

Solution

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < numbers.length; i++) {
            int diff = target-numbers[i];
            if (map.containsKey(numbers[i])) {
                res[0] = map.get(numbers[i])+1;
                res[1] = i+1;
            }
            map.put(diff, i);
        }
        return res;
    }
}

Brute Force

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int[] res = new int[2];
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    res[0] = i+1;
                    res[1] = j+1;
                }
            }
        }
        return res;
    }
}