图解两数之和：哈希表法
两数之和是一道非常经典，也非常高频的面试题，题目大意如下：
今天我们就一起探讨一下这道题的解法。
太长不看版
- 可以通过暴力运算，遍历
nums中的每一个元素，查找数组剩余部分是否有匹配的值； - 更高效的方式是利用哈希表key唯一且访问快的特性，建立
map存储未命中的值。遍历nums中的元素，查找map上是否有匹配的目标值，否则将当前元素存储到map上。
暴力运算法
暴力运算法很简单，通过首层for循环遍历数组中的每个元素curr，再通过另外一层for循环寻找target - curr值。
代码如下：
双层for循环导致暴力运算法时间复杂度为 O(n2)，在2020年的今天着实不能令大部分人满意。
哈希表法
哈希表（也叫散列表）是一种数据结构，其定义如下：
我们可以把它理解为词典，词典里的每个词条都是唯一的，在这个词条后面记录着词条的含义。就像查词典时我们能够很快速的定位到词条，哈希表的访问速度也非常快，其时间复杂度为O(1)。
在JavaScript中常规的键值对对象就是哈希表的实现。
接下来我们就结合题目中的case通过图解的方式来说明哈希表法如何计算两数之和。
0.初始化
初始化时我们会拿到nums数组[2, 1, 7, 11, 15]和target值9，同时map初始化为空对象{}用于存放未匹配成功的键值对：
接下来将遍历nums数组。
1.开始遍历数组
遍历开始，此时：
- 当前
map为空{}； - 当前索引值
index为0; - 当前索引对应的数值
curr为2; - 我们希望找到
target - curr即need值为7。
因为此时map为{}，所以map[need]值为undefined。
2.保存未匹配成功的值至map
因为所求为两数之和，所以哪怕nums[0]的值等于target，迭代第一步必然匹配失败。
此时将未能成功匹配的curr与index存放到map中。这一步非常重要，是整个解法的关键：
map[curr] = index;这里使用curr做为key，因为我们需要返回的结果是配对成功的数字其下标所构成的数组，匹配时是在map查找数字、返回下标。
3.继续遍历数组
匹配未成功，重复第一步，继续遍历数组：
同样未找到期望值need，继续将curr和index写入map：
继续重复此步骤直至匹配成功。
4.匹配成功！
继续遍历nums，此时need为2、curr为7,终于在map中查找到了need，隔空会师成功！
返回结果：[map[need], index]。map[need]在前的原因是map里存储的值，其下标一定在curr对应的下标之前。
5.完整示例代码
- 哈希解法每次查找的时间复杂度是O(1)，n次查找的时间复杂度O(n)；
- 空间复杂度也是O(n)，
map上最多存n个元素。
小结
- 双层
for循环暴力运算简单直观，时间复杂度O(n2)、空间复杂度O(1)； - 哈希表法时间复杂度和空间复杂度都是O(n)；
- 考察点是对哈希表这种数据结构的熟悉程度；
- 多一种解法就多一分胜算；
- 整体难度不高。
一入JS深似海，希望这个专栏能在你乘风破浪的旅途中有所帮助。欢迎关注我的公众号：「JS漫步指南」，更多精彩等待您发现！
以上是 图解两数之和：哈希表法 的全部内容， 来源链接： utcz.com/a/37934.html
