题目

描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3

输入:nums = [3,3], target = 6
输出:[0,1]

难度

简单

解法 1

/**
* 暴力穷举法
*/
public static int[] solution1(int[] nums, int target) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = i+1; j < nums.length; ++j) {
            if (nums[i] + nums[j] == target) {
                return new int[] {i, j};
            }
        }
    }
    return new int[0];
}

使用双重for循环,判断数组元素两两相加的值是否等于目标值,如果等于,则返回两个元素各自的下标,无匹配的情况返回空数组。
外层循环从左到右依次遍历元素,首轮内层循环遍历完成后若未找到正确答案数组,则第一个元素不属于正确答案数组元素之一,进行下一轮遍历,直至找到正确答案为止。

解法2

/**
 * 哈希法
 */
public static int[] solution2(int[] nums, int target) {
    HashMap<Integer, Integer> tempMap = new HashMap<Integer, Integer>(nums.length);
    for (int i = 0; i < nums.length; ++i) {
        if (tempMap.containsKey(target - nums[i])) {
            return new int[] {tempMap.get(target - nums[i]), i};
        }
        tempMap.put(nums[i], i);
    }
    return new int[0];
}

利用哈希表仅一层for循环就可得出答案。
先创建一个Integer类型同时作为key和value的HashMap,key是当前元素的值,value是当前元素在数组中的下标。比如target = 18, int[] nums = [1,5,7,11],循环三次的map结果是 {1=0, 5=1, 7=2} ,判断当前map是否存在正确值之一的key存在,不存在则添加到map中,存在则找到答案数组,直接返回。
上面的例子答案是 [2,3],循环遍历到7的时候,18 - 7 = 11,此时map中并没有11作为key存在,存入一个元素 key = 7, value = 2到map中,遍历到11的时候, 18 - 11 = 7,由于此前存入过7为key的键值对,可得11和7为正确答案,在返回他们对应下标的数组即可。

Q.E.D.


The best thing you can do at work hard.