LeetCode：两数之和

题目：

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

来源：力扣（LeetCode）

解：

注意，这道题返回的是下标，所以我们不会用排序后双指针去做，因为下标会乱。

暴力破解时间是O（n^2），但是我们可以采用Map进行查找映射，即不需要遍历，而是把值存进Map的key，下标作为value，这样就可以直接获得是否有对应的target-nums[i]值，时间为O（n）。注意不要反了，如果值作为value的话，还是遍历，那整体时间还是O（n^2）。

这道题简单在于答案唯一，也就是不存在相同的元素值，省了相同值处理。

import java.util.HashMap; class Solution { public int[] twoSum(int[] nums, int target) { int[] rs=new int[2]; HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>(); //你也可以先存，但是得判断target-nums[i]是否是nums[i]，因为元素只能用一次 //这里直接先判断，再存值，避免复用 for(int i=0;i<nums.length;i++){ if(hm.containsKey(target-nums[i])){ rs[0]=hm.get(target-nums[i]); rs[1]=i; return rs; }else{ hm.put(nums[i],i); } } return rs; } }