LeetCode 例题精讲 | 04 用双指针解 Two Sum：缩减搜索空间

点击关注上方“五分钟学算法”，

设为“置顶或星标”，第一时间送达干货。

转自面向大象编程

本期例题：LeetCode 167 – Two Sum II – Input array is sorted^[1]（Easy）

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数（不可以重复使用同一个数），返回两个数的下标值 i 和 j，要求 i < j。

假设每个输入有且仅有一个答案。

示例：

• 输入： numbers = [2, 7, 11, 15]， target = 9
• 输出： [0, 1]

（注意：这里和原题略有不同，下标改为从 0 开始，更自然。）

Two Sum 是 LeetCode 的第一道题，你们应该都见过。乍一看来，Two Sum II 这道题和 Two Sum 问题一样平平无奇。然而，这道题实际上内藏玄机，加上了数组有序的变化之后，它就换了一套解法。

如果你直接翻答案的话，会发现这就是一道普通的双指针解法。两个指针， 的时间。但是，如果你只看答案，没有理解背后的道理，就会陷入一看就会，一做就跪的困境。

实际上，在这个双指针解法背后蕴含的是缩减搜索空间的通用思想。那么，这篇文章将会为你细细讲述这个解法背后的道理，让你能真正地理解这道经典题目。同时，要做到下次遇到同类题目时，可以快速想到这种解法。

这篇文章将会包含：

• 双指针解法的正确性解释
• 双指针解法的背后原理：缩减搜索空间
• 相同原理的另一道例题讲解
• 相关题目

双指针的解法

在做 Two Sum II 之前，你可能已经知道 Two Sum 的解法。使用一个散列表，做一次线性遍历，可以得到  时间复杂度、  空间复杂度的解法。那么在 Two Sum II 中，数组有序这个变化，能帮助降低复杂度吗？

看到有序这个条件，你可能首先想到的是二分查找。但是仔细一想，需要固定一个数，对另一个数进行二分查找，这样时间复杂度是 ，显然不行。在不排序的情况下都做得到  时间、  空间。那么我们的目标只可能是： 的时间、 的空间！

那么怎么能做到呢？这就是本题的双指针解法了。让我们先看看答案是怎么写的：

public int[] twoSum(int[] nums, int target) {
    int i = 0;
    int j = nums.length - 1;
    while (i < j) {
        int sum = nums[i] + nums[j];
        if (sum < target) {
            i++;
        } else if (sum > target) {
            j--;
        } else {
            return new int[]{i, j};
        }
    }
    return new int[]{-1, -1};
}

代码的逻辑很简单，就轻轻巧巧地使用了两个指针，一个只向左移动，一个只向右移动。走完一趟，就得到了答案。

很多题解都只给出了这样一个答案，仿佛道理是不证自明的。但事实上，这个解法并不是能让人一眼就看懂。我第一次看到这道题的答案时，把这个解法叫做 Amazing O(n) 解法。这个解法的神奇之处在于，它把原本  的复杂度压缩到了 ，同时保证了算法的正确性。我们需要解释它为什么一定能得到解，而不会漏掉某些情况。

双指针解法的正确性解释

我们考虑两个指针指向的数字，A[i] 和 A[j]。由于数组是有序的，在一开始，A[i] 是数组中最小的数字，A[j] 是最大的数字。我们将 A[i] + A[j] 与目标和 target 进行比较，则可能有两种情况：

• A[i] + A[j] 大了。这时候，我们应该去找更小的两个数。由于 A[i] 已经是最小的元素了，将任何 A[i] 以外的数跟 A[j] 相加的话，和只会更大。因此 A[j] 一定不能构成正确的解，于是将 j 向左移动一格，排除 A[j]。
• A[i] + A[j] 小了。这时候，我们应该去找更大的两个数。由于 A[j] 已经是最大的元素了，将任何 A[j] 以外的数跟 A[i] 相加的话，和只会更小。因此 A[i] 一定不能构成正确的解，于是将 i 向右移动一格，排除 A[i]。

而第一步排除掉最左或最后的一个数后，我们再看子数组 A[i..j] ，其中 A[i] 又是最小的数字，A[j] 又是最大的数字。我们可以继续进行这样的排除。以此类推，进行  步，就可以排除掉所有可能的情况。

可以看到，无论 A[i] + A[j] 的结果是大了还是小了，我们都可以排除掉其中一个数。这样的排除法和二分搜索很相似。二分搜索通过每次排除一半的元素来减少比较的次数；而这道题的方法通过每次排除一个元素来减少比较的次数。两者又恰好都是利用了数组有序这个性质。

说到这里，这个解法的原理已经揭开一半了。接下来，我们再用更直观的方式，从搜索空间的角度真正地理解这道题。

搜索空间的缩减过程

在这道题中，我们要寻找的是符合条件的一对下标 ，它们需要满足的约束条件是：

• 、 都是合法的下标，即 
• （题目要求）

而我们希望从中找到满足 A[i] + A[j] == target 的下标 。以  为例，这时候全部的搜索空间是：

由于 、 的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间的大小是  数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是 。而更优的算法，则可以在一次操作内排除掉多个不合格的单元格，从而快速削减搜索空间，定位问题的解。

那么我们来看看，本题的双指针解法是如何削减搜索空间的。一开始，我们检查右上方单元格 ，即计算 A[0] + A[7] ：

假设 A[0] + A[7] 小于目标和，由于 A[7] 已经是最大的数，我们可以推出 A[0] + A[6] 、A[0] + A[5]、……、A[0] + A[1] 也都小于目标和，这些都是不合要求的解，可以一次排除，如下图所示。这相当于排除  的全部解，削减了一行的搜索空间，对应双指针解法中的 i++。

在削减一行搜索空间之后，剩余的搜索空间仍然是倒三角形状。我们检查右上方的单元格 ：

假设 A[1] + A[7] 大于目标和，此时需要排除  的全部解，削减一列搜索空间，对应双指针解法中的 j--：

以此类推，每次会削减一行或一列的搜索空间，经过  步以后，一定能检查完所有的可能性。搜索空间的减小过程如下面动图所示：

举一反三：二维矩阵搜索

Two Sum II 或许太过简单，并不需要用到搜索空间的知识。那么让我们来看看这个思想在另一个例题中的应用。

例题：LeetCode 240 – Search a 2D Matrix II^[2]（Medium）

一个  的矩阵 matrix 有如下特点：

• 每行的元素从左到右升序排列
• 每列的元素从上到下升序排列

写一个高效的算法在矩阵中搜索目标值 target。

这道题目的特点是，二维矩阵本身就是搜索空间，所以我们不需要思考搜索空间的形状，直接进行搜索即可。看到有序的这个条件，我们很容易想到使用二分搜索。二分搜索的中间点，显然应该是矩阵的中心点：

不过仔细思考就会发现，根据矩阵的性质，这个中心点把矩阵分成的四个部分中，只有左上部分全部小于中心点，只有右下部分全部大于中心点。也就是说做一次比较最多只能削减 1/4 的搜索空间。更大的问题是，删除掉左上部分或者右下部分之后，剩余的形状不再是一个规则的矩形，就无法继续进行二分搜索了。

那么我们不妨换一种思路，不追求一次削减一半的搜索空间，而是像刚才的 Two Sum II 问题那样，一次削减一行或者一列。类比刚才的双指针解法，我们可以检查矩阵右上角的元素，即 matrix[0][7]。

如果 matrix[0][7] 小于目标值，由于矩阵每行是有序的，同一行所有的元素肯定都小于目标值，就可以排除一行的元素。

而如果 matrix[0][7] 大于目标值，由于矩阵每列是有序的，同一列所有的元素一定都大于目标值，这又可以排除一列的元素。

那么，我们每次都必定可以排除一行或一列的元素。经过  次比较后，就可以搜索全部的矩阵。如果你仔细对比 Two Sum II 和这道题，会发现它们连削减搜索空间的方向都是一致的。

总结

从本文的例题可以看出，LeetCode 很多题目的答案很简单，但若想真正记住并举一反三，还是要理解题目背后的思想。Two Sum II 表面上是一个简单的双指针解法，但为了能想出这个解法，需要理解背后的搜索空间思想。

搜索空间的技巧需要在实际题目中灵活运用，本文中二维矩阵搜索例题的解法就是灵活运用了搜索空间思想。这里再列出一道和本题非常相关的题目，请仔细体会其中削减搜索空间的思想：

• 11. Container With Most Water^[3]

参考资料