题目描述
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的两个整数,并返回他们的数组下标。
注: 不能重复利用这个数组中同样的元素
解题思路
暴力大法
双重循环, 判断 a + b === targetNum
双重循环时间复杂度为 O(n^2)
Map 解法, 空间换时间
几乎所有的求和问题, 都可以转换为求差问题
使用
Map
来记录已经遍历过的数字及其下标 <value, index>
每次遍历新的数字时候,
targetNum
与当前数字做差, 查找 Map
中是否出现过, 出现过, 则返回两个下标; 未出现, 则继续循环/**
* @param {Number[]} nums
* @param {Number} target
*/
const findSumIndex = (nums, target) => {
const map = new Map()
for (let i = 0; i < nums.length; i++) {
// 判断差值是否在 map 中存在
if (map.has( target - nums[i])) {
// 存在, 则条件成立, 返回下标
return [map.get( target - nums[i]), i]
}
// 不存在则将当前值存入 map
map.set(nums[i], i)
}
}