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.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

这个题目比较简单，需要注意：

  1. array无序
  2. 返回index
  3. 数字可能有重复
  4. 只返回一个结果

方法1：HashTable

代码很简单就不多说什么了，时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            return new int[]{map.get(target - nums[i]), i};
        } else {
            map.put(nums[i], i);
        }
    }
    return new int[0];
}

方法2: sort + two pointers

方法1已经足够好了，写着玩，就把这种做法也写一下。时间复杂度O(nlogn)

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
27
28
29
30
31
32
33
34
class Point implements Comparable<Point> {
    int idx;
    int value;
    public Point(int idx, int value) {
        this.idx = idx;
        this.value = value;
    }
    @Override
    public int compareTo(Point that) {
        return this.value - that.value;
    }
}
public int[] twoSum(int[] nums, int target) {
    List<Point> list = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        list.add(new Point(i, nums[i]));
    }
    Collections.sort(list);
    int i = 0, j = nums.length - 1;
    while (i < j) {
        int sum = list.get(i).value + list.get(j).value;
        if (sum == target) {
            return new int[]{list.get(i).idx, list.get(j).idx};
        } else if (sum < target) {
            i++;
        } else {
            j--;
        }
    }
    return new int[0];
}