给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
一般简单思维
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i === j) continue;
if (nums[i] + nums[j] === target) {
return [j, i];
}
}
}
return result
};
image.png
虽然这种方法简单很容易想到，但是内存占用较大和效率低，。
简单优化一下
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i+1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
};
image.png
逆向思维
利用减法，用目标和减去当前的数字，然后再利用对象键值来找出目标差值。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let previewNum = {}
for(var i = 0; i< nums.length; i++) {
let curNum = nums[i]
let targetNum = target - curNum
let targetIndex = previewNum[targetNum]
if (targetIndex === undefined) {
previewNum[curNum] = i
} else {
return [i, targetIndex]
}
}
};
使用Map来实现
利用map.set把索引和数组中的值存入Map, 并利用map.has()判断对象中是否包含指定键，来查找目标差值，并使用map.get()方法获取目标差值的索引。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let map = new Map()
for(let i = 0; i< nums.length;i++){
let x = target - nums[i]
if(map.has(x)){
return [map.get(x), i]
}else{
map.set(nums[i],i)
}
}
};
image.png
