哈希-两数之和

在这里插入图片描述

求解代码

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


public int[] twoSum (int[] numbers, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] ans = {-1,-1};
        for(int i=0;i<numbers.length;i++){
            if(map.containsKey(target-numbers[i])){
                ans[0]= map.get(target-numbers[i])+1;
                ans[1]=i+1;
                break;
            }else{
                map.put(numbers[i], i);
            }
        }
        return ans;
    }

小贴士

对每个数字 numbers[i]，找之前已经遍历过的数字中，有没有 target - numbers[i]。

如果有，说明找到了答案。

那答案的两个下标就分别是：

之前的数的下标：map.get(target - numbers[i]) （map 里存的都是之前遍历过的数）

当前数的下标：i ，题目要求返回从 1 开始的下标，所以两个下标值都要 +1。

再说说返回的下标必须按升序排列：

由于HashMap 中存的元素的下标是「之前遍历的下标」，当前正在遍历的元素的下标是「现在的下标」，那必然满足「之前遍历的下标」 < 「现在的下标」，所以采用HashMap 解法能天然保证升序。