1.题目出处

2.我的解法

思路

由于这答案需要下标，于是我想到使用hashmap来转存数组，这样就可以对map排序并且导致下标不会发生变化。然后对map进行遍历，使用双指针从两头开始相加，寻找答案。

 public int[] twoSum(int[] numbers, int target) {
        // write code here
//        将数组存为hashMap
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            map.put(i, numbers[i]);
        }
//        对map进行排序
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> t1, Map.Entry<Integer, Integer> t2) {
//                升序排序
                return t1.getValue().compareTo(t2.getValue());
            }
        });

        int size = list.size();
        int[] array = new int[2];
        for (int i = 0, j = size-1; i < size && j < size && i<j; ) {
            Integer value = list.get(i).getValue();
            Integer value1 = list.get(j).getValue();
            if (value + value1 < target){
                i++;
            }else if (value + value1 > target){
                j--;
            }else {
//                System.out.println(value + "-----" + value1);
                int a = list.get(i).getKey() + 1;
                int b = list.get(j).getKey() + 1;
                if (a < b){
                    array[0] = a;
                    array[1] = b;
                }else{
                    array[0] = b;
                    array[1] = a;
                }
                break;
            }
        }

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

3.其他解法

思路

由于这个题的答案是唯一的并且一定有答案，所以大佬想到将值作为map的key存入map中，遍历数组的时候通过查找map的key中是否有和当前数字加起来等于target的值，有则返回，没有则继续向map中添加值。
我觉得这个方法比较聪明的点是

1.抓住这个题答案唯一性并且只有两个值这个特点，巧妙地利用map的contains**函数来解决问题
2.巧妙的利用了map只能通过键找值，不能通过值找键这个特性，将数组的值作为map的key，将数组下标作为map的value。这样就使后面找到值后无法锁定下标的难题。如果反过来将下标作为map的key，将数组的值作为value的话，就算同样的通过containsValue找到了值，后面为了锁定答案所在原数组的下标又要经过一些坎坷，此种解法无疑是下策。

public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < numbers.length; i++){
//            如果map中存在target-numbers[i]说明找到答案了，直接返回即可
            if(map.containsKey(target - numbers[i])){
                return new int[]{map.get(target - numbers[i])+1,i+1};
            }else {
                map.put(numbers[i], i);
            }
        }
        throw new IllegalArgumentException("No solution");
    }
1
2
3
4
5
6
7
8
9
10
11
12