给定一个整数数组
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]
提示
：
-
2 <= nums.length <= 10^3
-
-10^9 <= nums[i] <= 10^9
-
-10^9 <= target <= 10^9
-
只会存在一个有效答案
1.暴力法
使用两层循环，外层循环计算当前元素与 target 之间的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标。 时间复杂度：
O(n^2)
var twoSum = function(nums, target) {
for (var i = 0; i < nums.length; i++) {
var dif = target - nums[i];
// j = i + 1 的目的是减少重复计算和避免两个元素下标相同
for (var j = i + 1; j < nums.length; j++) {
if(nums[j] == dif)
return [i,j];
}
}
};
2.利用数组减少查询时间
在暴力法中，内层循环查找差值很浪费时间，那么如何减少查询时间呢？利用数组就可以减少查询时间。 使用一层循环，每遍历到一个元素就计算该元素与
target
之间的差值
dif
，然后以
dif
为下标到数组
temp
中寻找，如果
temp[dif]
有值(即不是
undefined
)，则返回两个元素在数组
nums
的下标，如果没有找到，则将当前元素存入数组
temp
中(下标:
nums[i], Value: i
) 。 时间复杂度：
O(n)
。
var twoSum = function(nums, target) {
var temp = [];
for(var i=0;i<nums.length;i++){
var dif = target - nums[i];
if(temp[dif] != undefined){
return [temp[dif],i];
}
temp[nums[i]] = i;
}
};
3.map字典索引查找
利用js原生的map字典索引来查找目标值，建立一个 { 值,下标 } 即{ key,value }模式的字典。
var twoSum = function(nums, target) {
var numsMap = new Map()
for(let i = 0; i < nums.length; i++) {
let dif = target - nums[i]
if (numsMap.has(dif) && numsMap.get(nums[i]) !== i) {
return [numsMap.get(nums[i]), i]
}
numsMap.set(nums[i], i)
}
}