[LintCode/LeetCode] Two Sum

NO IMAGE

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])]

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;
    }
}