BM50题解 | #两数之和#

Map 力扣第一题

有人夜里相爱，有人开车看海，有人力扣第一题做不出来

不要暴力，效率很低，如果遇到很长的陷阱用例可能无法AC

遍历数组，用一个HashMap来存数组中遇到的数

每次存之前先判断有没有当前这个numbers[i]的“另一半”，如果有就直接返回 i 和“另一半”的下标即可

众所周知，HashMap的值是可以重复的，但是key是唯一的，需求又是把两个值相加等于target

那么很明显，我们就应该把numbers[i]作为key，i 作为value，每次遍历numbers[i]，都判断map里有没有key和numbers[i]相加等于target的（map.containsKey()），如果没有就存进map，如果有直接把下标get出来返回，另一个下标是i，非常简单

注意：题目要求升序返回，先进map肯定是先被遍历到，发现没有“另一半”才进的map，所以当前下标i一定是比池子里的下标都大的

（可以试试把下标i作为key，numbers[i]作为value，每遍历一次numbers[i]都要遍历整个map，比较map.get(i) + numbers[i] == target，这样又变成暴力解法O(n^2)了，那还不如不用map，直接暴力数组，取的时候都是O(1)，存的时候还不用计算hash。多此一举）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; ++i) {
            if (map.containsKey(target - numbers[i])) {
                return new int[]{map.get(target - numbers[i])+1, i+1};
            }
            map.put(numbers[i], i);
        }
        return null;
    }
}