By

文章目录

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.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

直观做法是使用二重for循环，外循环遍历集合所有元素，内循环从当次被遍历元素的下一个，遍历至结尾，判断两个数sum后是否为target，耗时O(n²), 这样会超时。

可以考虑使用HashMap/HashTable，使用一重for循环，以numbers[i]为key，i作为value存入，这样只需遍历Map判断key=target-numbers[i]是否存在即可

两次for循环，一次插入，一次遍历判断，时间空间复杂度均为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> m = new HashMap<Integer, Integer>();// num => index

    Integer[] result = new Integer[2];
    for (int i = 0; i < numbers.length; i++) {
        if (target % 2 == 0 && numbers[i] == target / 2) {
            if (result[0] == null) {
                result[0] = i + 1;
            } else {
                result[1] = i + 1;
                return new int[]{result[0], result[1]};
            }
            continue;
        }
        m.put(numbers[i], i);
    }

    for (int num : m.keySet()) {
        if (m.containsKey(target - num)) {
            int a = m.get(num) + 1;
            int b = m.get(target - num) + 1;
            return a > b ? new int[]{b, a} : new int[]{a, b};
        }
    }
    return null;
}

在此基础上还可以进一步简化,让插入与判断可在一轮for循环内全部完成。原因如下：

题目说结果一定存在且唯一，不妨假设结果为a和b,a在前。虽然在遍历到a的时候b还不存在，但是遍历到后面的b时，a已经存在了，必然会达成判断条件map.contains(target-b)为true。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] twoSum(int[] numbers, int target) {
    int[] a = new int[2];
    Map<Integer, Integer> nums = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        //put number into hash table (if it's not already there)
        Integer n = nums.get(numbers[i]);
        if (n == null) nums.put(numbers[i], i); //subtract array element from target number
        n = nums.get(target - numbers[i]);
        if (n != null && n < i) {//if such number exists in the table return the indicies
            a[0] = n + 1;
            a[1] = i + 1;
            return a;
        }
    }
    return a;
}
文章目录