前端入门必刷题，经典算法—两数之和

优美的前⾔

年轻的码农哟~ 你是不是⼀直在思考⾃我提升的问题~
思来想去，决定从算法抓起（单押）~
拿起⼜放下，经历过多少次放弃（单押 ✖ 2）~
决定了！这次让我来帮你梳理（单押 ✖ 3）！Skr~

坦诚相⻅吧，两数之和！

《两数之和》是算法学习过程中最最经典也是最最基础的⼀个问题。

⼒扣、⽜客等刷题⽹站排⾏最⾼的就是两数之和了，经典就有其经典的道理，《两数之和》因为本身并没有太⾼的难度，⽽且也能体现出⼀些算法的思想，所以作为⼊⻔必刷题来说，再合适不过了。

那么咱们先来看题目吧

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

我们来详细分析一下题目，首先有一个给定的数组, 数组内有若干数字

var nums = [ 11, 15, 3, 8, 2, 6 ]

确定一个目标值

var target = 9

接下来就是需求分析

从给出的 nums 数组中找到两个数字, 两个数字的和是 target，有且只有一个唯一解，找到两个数字以后, 返回两个数字的下标

比如这里的答案就是 2 和 5，因为 nums[2] + nums[5] = 9 符合要求

作为一个入门的程序员, 一个小趴菜, 我都觉得这个玩意对于我来说实在是太简单了

明⽩了！挨个对⽐挨个找⼀遍不就得了，小小问题，难不倒真正的勇⼠，双重循环暴⼒解法奉上！

var twoSum = function(nums, target) {for (var i = 0; i < nums.length; i++) {for (var j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] === target) {return [ i, j ]}}}
}

完全没有问题, 搞定, 我真是太棒了
给我的小伙伴们看完这个答案以后, 我的嘴角微微上扬, 已经准备好接受大家的表扬了

等等，你们这是什么眼神, 我怎么了, 难道不对吗 ??

提交上去之后，分数并不⾼，说这种⽅法性能不好，暴⼒解法采⽤双重循环嵌套的话，虽然解决了问题，但是执⾏判断的次数⼤约是：(n-1) + (n-2) + (n-3) + … + 1次

从之前学过的时间复杂度来分析的话，暴⼒解法的时间复杂度⼤约是O(n(n-1))即O(n²-n)，虽然时间复杂度⼩于O(n²)，但是实际也没好到哪⼉去，当然分数不⾼咯。

好吧，好吧，真是拿你没有办法（扶眼镜）~，接下来，我们来转换思路，另辟蹊径！

秘法 · 空间换时间

所谓的空间换时间，其实指的就是，针对这样两层遍历的情况，我们可以在遍历的过程中，⼀边去判断，⼀边做存储，判断，找到了就返回，没找到，那就存起来等到下⼀次判断的时候看看是否能找的到

这样⼀边判断、⼀边存储的⽅式当然快咯，因为毕竟只需要遍历⼀次嘛，呐，举个栗⼦：

有⼀队⼩朋友，要找到他们做任务的搭档，我们就可以先挨个把⼩朋友叫过来（开始遍历），让他从⼀个本⼦上去找，看本 ⼦上的照⽚有没有⾃⼰的搭档（做判断）。
如果找到了，那⼩朋友就可以⼤声报告出来（返回结果），如果没找到呢，就把这个⼩朋友的照⽚贴在本⼦上，然后叫下⼀ 个⼩朋友进来找（存储后继续遍历）。
这样是不是性能和效率就⾼很多了，⾮常Nice，换个思路，果然有另外收获！

好了，开打，开打！代码奉上！

// 空间换时间解法
const twoSum = (nums, target) => {
// 创建⼀个Map对象的数据，键值对中键为数组中的元素与⽬标的差值，值为这个元素的索引
const map = new Map(); // 存储⽅式 {key使⽤⽬标差值=>值使⽤索引存储}
// 开始遍历数组
for (let i = 0; i < nums.length; i++) {
// 先算出当前这个元素匹配的元素应该是⼏
let diff = target - nums[i]
// ⼀边顺⼿做判断，找到啦！就返回
// 判断map中是否有符合⽬标差值的键名,有则返回对应的索引(map中对应的值)及当前遍历数组的索引
if (map.has(diff)) {
return [map.get(diff), i];}
// ⼀边做存储，没找到，就存起来！
// 如果map中没找到符合⽬标差值的键名,则将本次循环数组获取的数组元素作为键名,及索引作为键值写⼊到map中记录
map.set(nums[i], i);}
};

这次的⽅法，我们只⽤了⼀次循环，就解决了问题，时间复杂度当然就是O(n)咯，只是在函数运⾏的过程中，创造了⼀个 map对象在占⽤内存空间，虽然函数之后map对象被回收了，但是总的来说是消耗了⼀些内存的。
但是虽然计算的时候占⽤了内存，但是⾮常明显的提⾼了效率和性能，ok，ok，得偿所愿！

最后画重点！

所以说，所谓的空间换时间，真的⾮常适合⽤在⼀些查找类的算法需求中，以后再碰到这样的需求，我们不要再研究双重循环嵌套查找啦，来尝试下空间！换！时间吧！

好了，这期经典算法–两数之和就介绍到这，你学废了吗？

少年！咱们下期再⻅ヾ(￣▽￣)Bye_Bye