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

给定一个整数数组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(n2)，在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(n2)、空间复杂度O(1)；
  • 哈希表法工夫复杂度和空间复杂度都是O(n)；
  • 考察点是对哈希表这种数据结构的相熟水平；
  • 多一种解法就多一分胜算；
  • 整体难度不高。

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