关于javascript:图解两数之和哈希表法

两数之和是一道十分经典，也十分高频的面试题，题目粗心如下：

给定一个整数数组 nums 和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
case:
给定 nums = [2, 1, 7, 11, 15], target = 9
因为 nums[0] + nums[2] = 2 + 7 = 9
所以返回 [0, 2]

明天咱们就一起探讨一下这道题的解法。

太长不看版

• 能够通过暴力运算，遍历 nums 中的每一个元素，查找数组残余局部是否有匹配的值；
• 更高效的形式是利用哈希表 key 惟一且拜访快的个性，建设 map 存储未命中的值。遍历 nums 中的元素，查找 map 上是否有匹配的目标值，否则将以后元素存储到 map 上。

暴力运算法

暴力运算法很简略，通过首层 for 循环遍历数组中的每个元素 curr，再通过另外一层for 循环寻找 target - curr 值。

代码如下：

双层 for 循环导致暴力运算法工夫复杂度为 O(n²)，在 2020 年的明天着实不能令大部分人称心。

哈希表法

哈希表（也叫散列表）是一种数据结构，其定义如下：

哈希表是依据关键字（Key value）而间接拜访在内存存储地位的数据结构。

咱们能够把它了解为词典，词典里的每个词条都是惟一的，在这个词条前面记录着词条的含意。就像查词典时咱们可能很疾速的定位到词条，哈希表的访问速度也十分快，其工夫复杂度为 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(n²)、空间复杂度 O(1)；
• 哈希表法工夫复杂度和空间复杂度都是 O(n)；
• 考察点是对哈希表这种数据结构的相熟水平；
• 多一种解法就多一分胜算；
• 整体难度不高。

一入 JS 深似海，心愿这个专栏能在你乘风破浪的旅途中有所帮忙。欢送关注我的公众号：「JS 散步指南」，更多精彩期待您发现！