图解两数之和：双指针法
两数之和是一道非常经典，也非常高频的面试题，题目大意如下：
之前我们探讨了这个问题的暴力运算法和哈希表法，今天我们使用双指针法来解决它。
太长不看版
- 首先排序数组；
- 使用
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漫步指南」，更多精彩等待您发现！
以上是 图解两数之和：双指针法 的全部内容， 来源链接： utcz.com/a/38674.html
