图解双指针法

发表于 2020-08-18 更新于 2024-02-27 分类于 develop 阅读次数：

两数之和是一道非常经典，也非常高频的面试题。

给定一个整数数组nums 和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

例子：

## 给定
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中我们使用 碰撞指针 的方式来实现，其它两种套路会在后续文章中介绍。

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

所以在两数之和中我们需要先将目标数组进行排序：

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

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

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

从这里就可以看出，为什么对有序数组才适用碰撞指针。

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

与步骤2类似，当sum小于target时我们需要右移左指针，增加sum值使得两者更加接近：

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

示例代码如下：

需要注意的是，由于JavaScript引用类型的特性，我们首先拷贝了nums，才使用Array.sort对拷贝数组进行排序。

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

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

以上全文转载于 JS漫步指南 的文章：