原题：

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

难点，原数组是未排序，且可能有重复，例如测例

Input: numbers={0, 1, 4, 0}, target=0

Output: index1=1, index2=4

经典的方法，复制数组，排序，两头往中间扫描，找到之后再在原数组来一趟扫描求得原index

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] num = numbers.clone();
        Arrays.sort(num);

        int length = numbers.length;
        int left = 0;
        int right = length - 1;
        int sum = 0;

        ArrayList<Integer> index = new ArrayList<Integer>();

        while (left < right) {
            sum = num[left] + num[right];

            if (sum == target) {
                for (int i = 0; i < length; ++i) {
                    if (numbers[i] == num[left]) {
                        index.add(i + 1);
                    } else if (numbers[i] == num[right]) {
                        index.add(i + 1);
                    }
                    if (index.size() == 2) {
                        break;
                    }
                }
                break;
            } else if (sum > target) {
                --right;
            } else {
                ++left;
            }
        }

        int[] result = new int[2];

        result[0] = index.get(0);
        result[1] = index.get(1);

        return result;
    }

    public static void main(String[] args) {
        Solution slt = new Solution();

        int[] numbers = { 2, 7, 11, 15 };
        int target = 9;

        int[] index = new int[2];

        index = slt.twoSum(numbers, target);

        System.out.println("index1=" + index[0] + ", index2=" + index[1]);
    }
}

暴力的直接用Hash

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] indices = new int[2];
        int len = numbers.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int i = 0; i < len; i++) {
            if (!map.containsKey(numbers[i])) {
                map.put(target - numbers[i], i);
            } else {
                indices[0] = map.get(numbers[i]) + 1;
                indices[1] = i + 1;
            }
        }
        return indices;
    }
}