image.png

最开始的想法是肯定不能查询一个数后在查所有后面的数，这样时间复杂度O(n2)。
如果先排序的再搜素，时间复杂度取决于排序的时间复杂度O(nlgn)。
肯定是利用hash原理扫一遍，再查。如果数组有重复的值，那么hash的value就直接用List。

public int[] twoSum(int[] nums, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>(); //key:值 value：位置列表
        //hash
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.get(nums[i]).add(i);
            }else {
                List list = new ArrayList();
                list.add(i);
                map.put(nums[i],list);
            }
        }
        for(int i=0;i<nums.length;i++){
            // 如果存在剩下的值
            if(map.containsKey(target-nums[i])){
                List<Integer> list = map.get(target - nums[i]);
                //待找值和减去的值相同，判断数组是否多余两个值
                if(target-nums[i]==nums[i]){
                    if(list.size()>=2){
                        return new int[]{list.get(0),list.get(1)};
                    }
                }else {
                    return new int[]{i,map.get(target-nums[i]).get(0)};
                }
            }else {
                continue;
            }
        }
        return new int[]{0,0};
    }