2.2 双指针

双指针是一种常用的解题思路，可以使用两个相反方向或相同方向的指针扫描数组从而达到解题目的。值得注意的是，本书在不同的章节都提到了双指针。本书中的“指针”并不专指C语言中的指针，而是一个相对宽泛的概念，是能定位数据容器中某个数据的手段。在数组中它实际上是数字的下标。

方向相反的双指针经常用来求排序数组中的两个数字之和。一个指针P₁指向数组的第1个数字，另一个指针P₂指向数组的最后一个数字，然后比较两个指针指向的数字之和及一个目标值。如果两个指针指向的数字之和大于目标值，则向左移动指针P₂；如果两个指针指向的数字之和小于目标值，则向右移动指针P₁。此时两个指针的移动方向是相反的。

方向相同的双指针通常用来求正数数组中子数组的和或乘积。初始化的时候两个指针P₁和P₂都指向数组的第1个数字。如果两个指针之间的子数组的和或乘积大于目标值，则向右移动指针P₁删除子数组最左边的数字；如果两个指针之间的子数组的和或乘积小于目标值，则向右移动指针P₂在子数组的右边增加新的数字。此时两个指针的移动方向是相同的。

下面用双指针来解决几道典型的数组面试题。

面试题6：排序数组中的两个数字之和

分析：在面试的时候很多人都能想到这个问题最直观的解法，就是先在数组中固定一个数字，再依次判断数组中其余的数字与它的和是不是等于k。如果数组的长度是n，由于需要对每个数字和其他n-1个数字求和，因此这种解法的时间复杂度是O（n²）。

上述解法可以用二分查找来优化。假设扫描到数字i，如果数组中存在另一个数字k-i，那么就找到了一对和为k的数字。我们没有必要通过从头到尾逐个扫描数组中的每个数字来判断数组中是否存在k-i。由于数组是递增排序的，因此可以用二分查找在数组中搜索k-i。二分查找的时间复杂度是O（logn），因此优化之后的解法的时间复杂度是O（nlogn）。

上述解法还可以用空间换时间进行优化。可以先将数组中的所有数字都放入一个哈希表，然后逐一扫描数组中的每个数字。假设扫描到数字i，如果哈希表中存在另一个数字k-i，那么就找到了一对和为k的数字。判断哈希表中是否存在一个数字的时间复杂度是O（1），因此新解法的时间复杂度是O（n），同时它需要一个大小为O（n）的哈希表，空间复杂度也是O（n）。

存在时间复杂度是O（n）、空间复杂度是O（1）的解法。我们用两个指针P₁和P₂分别指向数组中的两个数字。指针P₁初始化指向数组的第1个（下标为0）数字，指针P₂初始化指向数组的最后一个数字。如果指针P₁和P₂指向的两个数字之和等于输入的k，那么就找到了符合条件的两个数字。如果指针P₁和P₂指向的两个数字之和小于k，那么我们希望两个数字的和再大一点。由于数组已经排好序，因此可以考虑把指针P₁向右移动。因为在排序数组中右边的数字要大一些，所以两个数字的和也要大一些，这样就有可能等于输入的数字k。同样，当两个数字的和大于输入的数字k时，可以把指针P₂向左移动，因为在排序数组中左边的数字要小一些。

下面以数组[1，2，4，6，10]及目标期待的和8为例详细分析这个过程。首先定义两个指针，第1个指针P₁指向数组的第1个数字1（下标为0的数字），第2个指针P₂指向数组的最后一个数字10。这两个数字的和11大于8，因此把第2个指针P₂向左移动一个数字，让它指向6。这个时候两个数字1与6的和是7，小于8。接下来把指针P₁向右移动一个数字指向2。此时两个数字2与6的和是8，正是我们期待的结果。表2.1总结了在数组[1，2，4，6，10]中查找和为8的数对的过程。

这种利用两个指针的解法可以用如下Java代码实现：

在上述代码中，变量i相当于指针P₁，变量j相当于指针P₂。由于上述代码中只有一个while循环，循环执行的次数最多等于数组的长度，因此这种思路的时间复杂度是O（n）。

面试题7：数组中和为0的3个数字

分析：这个题目是面试题6的加强版。如果输入的数组是排序的，就可以先固定一个数字i，然后在排序数组中查找和为-i的两个数字。我们已经有了用O（n）时间在排序数组中找出和为给定值的两个数字的方法，由于需要固定数组中的每个数字，因此查找三元组的时间复杂度是O（n²）。

前面只需要O（n）时间在数组中找出和为给定值的两个数字的方法只适用于排序数组。可是这个题目并没有说给出的数组是排序的，因此需要先对数组排序。排序算法的时间复杂度通常是O（nlogn），因此这种解法的总的时间复杂度是O（nlogn）+O（n²），仍然是O（n²）。

还剩下一个问题是如何去除重复的三元组。前面提到需要使用两个指针来找出和为给定值的两个数字。在找到一个和为0的三元组之后，就需要移动这两个指针，以便找出其他符合条件的三元组。在移动指针的时候需要跳过所有相同的值，以便过滤掉重复的三元组。

上述代码先对数组进行排序。在固定用变量i指向的数字之后，函数twoSum在排序后的数组中找出所有下标大于i并且和为-nums[i]的两个数字（下标分别为j和k）。如果nums[i]、nums[j]、nums[k]的和大于0，那么下标k向左移动；如果nums[i]、nums[j]、nums[k]的和小于0，那么下标j向右移动。如果3个数字之和正好等于0，那么向右移动下标j，以便找到其他和为-nums[i]的两个数字。

由于要避免重复的三元组，因此函数twoSum使用一个while循环让下标j跳过重复的数字。基于同样的原因，函数threeSum中也有一个while循环让下标i跳过重复的数字。

面试题8：和大于或等于k的最短子数组

分析：子数组由数组中一个或连续的多个数字组成。一个子数组可以用两个指针表示。如果第1个指针P₁指向子数组的第1个数字，第2个指针P₂指向子数组的最后一个数字，那么子数组就是由这两个指针之间的所有数字组成的。

指针P₁和P₂初始化的时候都指向数组的第1个元素。如果两个指针之间的子数组中所有数字之和大于或等于k，那么把指针P₁向右移动。每向右移动指针P₁一步，相当于从子数组的最左边删除一个数字，子数组的长度也减1。由于数组中的数字都是正整数，从子数组中删除一些数字就能减小子数组之和。由于目标是找出和大于或等于k的最短子数组，因此一直向右移动指针P₁，直到子数组的和小于k为止。

如果两个指针之间的子数组中所有数字之和小于k，那么把指针P₂向右移动。指针P₂每向右移动一步就相当于在子数组的最右边添加一个新的数字，子数组的长度加1。由于数组中的所有数字都是正整数，因此在子数组中添加新的数字能得到更大的子数组之和。

下面以数组[5，1，4，3]为例一步步分析用两个指针找出和大于或等于7的最短子数组的过程。首先，指针P₁和P₂都指向数组中的第1个数字5。此时子数组中只有一个数字5，因此子数组中的所有数字之和也是5，小于7。然后把指针P₂向右移动一步指向数字1。此时子数组中包含两个数字，即5和1，它们的和为6，仍然小于7。因此，再把指针P₂向右移动一步指向数字6，此时数组中包含3个数字，即5、1和4，它们的和是10，大于7。由此找到了一个和大于7的子数组，它的长度是3。

下面尝试把指针P₁向右移动一步，确定是否能找到更短的符合要求的子数组。移动指针P₁之后，子数组中包含两个数字，即1和4，小于7。然后将指针P₂向右移动一步指向数字3。此时子数组中包含3个数字，即1、4和3，它们的和为8。此时又找到了和大于7的子数组，它的长度也是3。

下面尝试再把指针P₁向右移动一步，使指针P₁指向数字4。此时子数组中包含两个数字，即4和3，它们的和是7。这个子数组的长度是2。

如果再一次把指针P₁向右移动一步指向数字3，那么子数组中只包含一个数字3，子数组中的所有数字之和为3，小于7。按照移动指针的规则，此时应该把指针P₂向右移动。由于此时指针P₂已经指向数组中的最后一个数字，因此无法再向右移动。这说明已经尝试了所有的可能性，可以结束这个查找过程了。

上述思路可以总结如下：当指针P₁和P₂之间的子数组数字之和小于k时，向右移动指针P₂，直到两个指针之间的子数组数字之和大于k，否则向右移动指针P₁，直到两个指针之间的子数组数字之和小于k。表2.2总结了查找数组[5，1，4，3]中和大于或等于7的最短子数组的过程。

有了清晰的思路之后再编写代码就比较容易。参考代码如下：

在上述代码中，变量left是子数组中第1个数字的下标，相当于指针P₁，而变量right是子数组中最后一个数字的下标，相当于指针P₂。变量sum是位于两个指针之间的子数组中的所有数字之和。

最后分析这种解法的时间复杂度。假设数组的长度为n，尽管上述代码中有两个嵌套的循环，该解法的时间复杂度仍然是O（n）。这是因为在这两个循环中，变量left和right都是只增加不减少，变量right从0增加到n-1，变量left从0最多增加到n-1，因此总的执行次数是O（n）。

面试题9：乘积小于k的子数组

分析：虽然这个题目是关于子数组数字的乘积的，和面试题8（关于子数组数字之和）看起来不太一样，但求解的思路大同小异，仍然可以利用两个指针求解。

和面试题8一样，用指针P₁和P₂指向数组中的两个数字，两个指针之间的数字组成一个子数组。指针P₁永远不会走到指针P₂的右边。两个指针初始化都指向数组的第1个数字（下标为0的数字）。

如果两个指针之间的子数组中数字的乘积小于k，则向右移动指针P₂。向右移动指针P₂相当于在子数组中添加一个新的数字，由于数组中的数字都是正整数，因此子数组中数字的乘积就会变大。

如果两个指针之间的子数组中数字的乘积大于或等于k，则向右移动指针P₁。向右移动指针P₁相当于从子数组中删除最左边的数字，由于数组中的数字都是正整数，因此子数组中数字的乘积就会变小。

由于我们的目标是求出所有数字乘积小于k的子数组的个数，一旦向右移动指针P₁到某个位置时子数组的乘积小于k，就不需要再向右移动指针P₁。这是因为只要保持指针P₂不动，向右移动指针P₁形成的所有子数组的数字乘积就一定小于k。此时两个指针之间有多少个数字，就找到了多少个数字乘积小于k的子数组。

基于这种思路的Java代码如下所示：

和面试题8的代码类似，在上述代码中，变量left是子数组中第1个数字的下标，相当于指针P₁，而变量right是子数组中最后一个数字的下标，相当于指针P₂。变量product是位于两个指针之间的子数组中的所有数字的乘积。

和面试题8一样，这种解法的时间复杂度也是O（n）。请读者自行分析，这里不再重复介绍。