两数之和我相信,大家对这道题目都不陌生,为什么突然说道这道题目呢,是因为有个朋友来问我,如果是你最优的解决方法是什么。
首先,这个两数之和,不是有些人想着的那种,让你求1+1 = 2。
我来举个案例:如果有个数组nums = [2,7,11,15], 求和数target = 9,输出的值是[0,1],因为数组的第一个值和第二个值加起来是9,这就是本章节要说的两数求和。
我们要用js的方式,去写一个方法实现,这个两数之和。当时我的第一反应就是双重for循环,判断,第一次的循环和第二次的循环相加的结果是不是我的目标值,如果是那就return出结果,但是这种方法太浪费时间,过于暴力,有点呆头鹅。
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]
}
}
}
}
解析:上面代码的思路,第一次循环,我们直接循环数组nums,然后第二次循环,我们不从0开始,而是从第一次循环的后一个开始,因为你不可能是重复的,当第一次循环的值 + 第二次循环的值,等于我们的目标和的时候,就拿到第一次循环的下标值和第二次循环的下标值了。
上述的方法是可以实现的,但是为了减少时间,我们尽量用一次循环,所以我参考了,别的大佬给出的思路,这个思路,我当时确实没有想到,所以和大家分享一下,可以先看下代码,备注我也写在了里面。
var twoSum = function (nums, target) {
const prevNums = {}; // 存储出现过的数字,和对应的索引
for (let i = 0; i < nums.length; i++) { // 遍历元素
const curNum = nums[i]; // 当前元素
const targetNum = target - curNum; // 满足要求的目标元素
const targetNumIndex = prevNums[targetNum]; // 在prevNums中获取目标元素的索引
if (targetNumIndex !== undefined) { // 如果存在,直接返回 [目标元素的索引,当前索引]
return [targetNumIndex, i];
} else { // 如果不存在,说明之前没出现过目标元素
prevNums[curNum] = i; // 存入当前的元素和对应的索引
}
}
};
解析:这里用到了一次的循环,首先定义了一个空的对象,然后我们进行循环,循环之后,我们可以拿到这个数组中的每一个,也就是2,7,11,15,然后,我们需要的目标数分别就是,7,2,-2,-6,这时候我们就要看之前定义空对象的元素了,看看这个目标数是不是在这个对象里面,如果有,那么我们可以直接拿到符合要求的两个下标值,如果不能的话,我们就将索引存入之前定义的空对象内。很显然,我们第一次循环判断的时候,肯定走的else里面的,那么,此时存入的下标值就是0,就相当于是prevNums = {2:0},然后走下一回,那么此时,targetNumIndex是有值的,是0,我们就直接拿到了目标数组[0,1]
当然了,说到这里,有人会觉得,写的很复杂,有点啰嗦,官方的话是给了个简精版本的,我也给大家看一下,就是你明白了原理之后,简化起来你也能看懂
var twoSum = function (nums, target) {
let map = {}
for (let i = 0; i < nums.length; ++i) {
const rest = target - nums[i];
if (map[rest] !== undefined) {
// 注意这里map里面的是下标比较小的值。
return [map[rest], i]
}
map[nums[i]] = i
}
return []
}
解析:为什么说是精简版本呢,你会发现,其实就少了几个赋值的步骤,还有就是多了一个如果数组和目标和不一致的话,就返回一个空数组。这个运行过程和上面是一个意思,这里就不再讲一遍了。
最后我看到了另一位大佬的想法,他的想法是合理利用ES6的map数据结构来完成
var twoSum = function (nums, target) {
var map = new Map()
for (let i = 0; i < nums.length; i++) {
x = target - nums[i]
if (map.has(x)) {
return [map.get(x), i]
}
map.set(nums[i], i)
}
}
解析:map,有几个用法,首先,我们用map来存放{数组元素值,坐标}这样的键值对,这里我们循环,然后用set方法去存放,每一个值和对应的下标,然后我们用has去判断这个map里面有没有目标元素,如果有的话,我们就能拿到这两个下标,就会用到get,获取到map存放的下标了。基本上来讲的话,都是需要一定的逆向思维去反推得到结论。
好了,到这里,我们基本上就说完了解决这道题目我能想得出来的一些方法,当然咯,为了方便大家日后遇到,或者需要这种方法,我给大家特地,写完整了一些,这些方法你们想用哪个用哪个,能一次循环结束,就不要用两个循环
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
* * 示例:
* 输入:nums = [2,7,11,15], target = 9
* 输出:[0,1]
* 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
*/
var twoSum = function (nums, target) {
let map = {}
for (let i = 0; i < nums.length; ++i) {
const rest = target - nums[i];
if (map[rest] !== undefined) {
// 注意这里map里面的是下标比较小的值。
return [map[rest], i]
}
map[nums[i]] = i
}
return []
}
ps:分享一首歌,来自小阿七的《从前说》,为什么分享呢,有时候可能不是因为歌曲好听,而是你感同身受,是你有了故事,所以歌曲才富有了色彩吧。