[LintCode/LeetCode] Two Sum

xiaoxiaozi 發(fā)布于2019-08-14 15:22 / 1020人閱讀

摘要：就不說了，使用的解法思路如下建立，對應(yīng)該元素的值與之差，對應(yīng)該元素的。然后，循環(huán)，對每個元素計算該值與之差，放入里，。如果中包含等于該元素值的值，那么說明這個元素正是中包含的對應(yīng)的差值。返回二元數(shù)組，即為兩個所求加數(shù)的序列。

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，key對應(yīng)該元素的值與target之差，value對應(yīng)該元素的index。
然后，循環(huán)，對每個元素numbers[i]計算該值與target之差，放入map里，map.put(target-numbers[i], i)。
如果map中包含等于該元素值的key值，那么說明這個元素numbers[i]正是map中包含的key對應(yīng)的差值diff(=target-numbers[map.get(numbers[i])])。那么，返回map中對應(yīng)元素的index+1放入res[0]，然后將i+1放入res[1]。返回二元數(shù)組res，即為兩個所求加數(shù)的index序列。

Solution

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        Map 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;
    }
}