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

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

之前咱们探讨了这个问题的暴力运算法和哈希表法，明天咱们应用双指针法来解决它。

太长不看版

  • 首先排序数组；
  • 应用left，right两个指针；
  • 比拟target与left值加right值的和，挪动对应的指针；
  • 双指针解法的工夫复杂度取决于对应的排序算法，空间复杂度为O(n)。

什么是双指针？

双指针和疾速排序、冒泡排序等具体算法不同。它更靠近于一种思（tào）路，一种应用两个指针互相配合来存储节点以便于运算的技巧。

双指针法实用于数组、链表等线性数据结构，罕用的思路有：碰撞指针、滑动窗口、快慢指针等。

在两数之和这个case中咱们应用碰撞指针的形式来实现，其它两种套路会在后续文章中介绍。

0.排序

所谓碰撞指针，是指在有序数组中定义left（数组起始地位）、right（数组终止地位）两个指针，在遍历时依据对应条件的不同来判断应该挪动哪个指针，进而从数组两端遍历数组。

所以在两数之和中咱们须要先将指标数组进行排序：

排序算法的工夫复杂度决定了整个计算的工夫复杂度。因为双指针遍历的复杂度是O(n)。

1.创立双指针

在排好序的数组（以下简称数组）两端别离创立left、right指针：

2.左移右指针

此时left值与right值之和（以下简称sum）大于target，此时应该将right左移一位，减小sum使其更靠近target。

从这里就能够看出，为什么对有序数组才实用碰撞指针。

3.持续遍历数组

在这个case中咱们须要持续遍历数组，直到right指针指向7，此时sum小于target：

4.右移左指针

与步骤2相似，当sum小于target时咱们须要右移左指针，减少sum值使得两者更加靠近：

5.匹配胜利！

在以后case中，left指向2时sum与target相等，匹配胜利！
此时返回left值和right值在原数组中的下标即可：

6.残缺示例代码

示例代码如下：

须要留神的是，因为JavaScript援用类型的个性，咱们首先拷贝了nums，才应用Array.sort对拷贝数组进行排序。

另外，对于nums=[1,2,2,3],target=4这种case，其冀望的返回值是[1,2]而不是[1,1]或者[2,2]。所以这里咱们应用了Array.lastIndexOf()这个API。

小结

  • 采纳碰撞双指针进行运算；
  • 碰撞双指针运算的工夫复杂度取决于具体的排序算法，空间复杂度为O(n)；
  • 碰撞指针须要对数组进行排序；
  • 排序时留神不要净化原数组；
  • 返回后果须要思考数组含有雷同项；

再温习一下暴力运算法和哈希表法：

  • 双层for循环暴力运算简略直观，工夫复杂度O(n2)、空间复杂度O(1)；
  • 哈希表法工夫复杂度和空间复杂度都是O(n)；
  • 考察点是对哈希表这种数据结构的相熟水平；
  • 多一种解法就多一分胜算；
  • 整体难度不高。

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