leetcode_01_两数之和
2020-01-27 本文已影响0人
NWPU_HaiboWu
1. 题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
2.示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
3.思路分析
不能重复利用这个数组中同样的元素：意味着时间复杂度要为O(n)
通常，如果采用暴力法，则用两层循环，外层循环计算当前元素与 target 之间的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标，时间复杂度：O(n^2)。 内层循环查找差值很浪费时间，那么如何减少查询时间呢？利用 HashMap ！
4.代码实现
class Solution {
public int[] twoSum(int[] nums, int target) {
int []res=new int[2];
Map map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
res[0]=i;
res[1]=map.get(nums[i]);
return res;
}
map.put(target-nums[i],i);
}
}
}
