1. 題目描述
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，你不能重復(fù)利用這個數(shù)組中同樣的元素。
2.示例
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
3.思路分析
不能重復(fù)利用這個數(shù)組中同樣的元素：意味著時間復(fù)雜度要為O(n)
通常，如果采用暴力法，則用兩層循環(huán)，外層循環(huán)計算當(dāng)前元素與 target 之間的差值，內(nèi)層循環(huán)尋找該差值，若找到該差值，則返回兩個元素的下標(biāo)，時間復(fù)雜度：O(n^2)。 內(nèi)層循環(huán)查找差值很浪費(fèi)時間，那么如何減少查詢時間呢？利用 HashMap ！
4.代碼實(shí)現(xiàn)
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);
}
}
}
