面向大象编程
本期例题：LeetCode 167 - Two Sum II - Input array is sorted[1]（Easy）
给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数（不可以重复使用同一个数），返回两个数的下标值 i 和 j，要求 i < j。
假设每个输入有且仅有一个答案。
示例：
（注意：这里和原题略有不同，下标改为从 0 开始，更自然。）
- 输入： numbers = [2, 7, 11, 15]， target = 9
- 输出： [0, 1]
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
的下标
。以
下标 i, j 的搜索空间
由于
、
的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间的大小是
数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是
。而更优的算法，则可以在一次操作内排除掉多个不合格的单元格，从而快速削减搜索空间，定位问题的解。
那么我们来看看，本题的双指针解法是如何削减搜索空间的。一开始，我们检查右上方单元格
，即计算
A[0] + A[7]
：
检查单元格 0, 7
假设
A[0] + A[7]
小于目标和，由于
A[7]
已经是最大的数，我们可以推出
A[0] + A[6]
、
A[0] + A[5]
、……、
A[0] + A[1]
也都小于目标和，这些都是不合要求的解，可以一次排除，如下图所示。这相当于排除
的全部解，削减了一行的搜索空间，对应双指针解法中的
i++
。
排除 i = 0 的全部解
在削减一行搜索空间之后，剩余的搜索空间仍然是倒三角形状。我们检查右上方的单元格
：
检查单元格 1, 7
假设
A[1] + A[7]
大于目标和，此时需要排除
的全部解，削减一列搜索空间，对应双指针解法中的
j--
：
排除 j = 7 的全部解
以此类推，每次会削减一行或一列的搜索空间，经过
搜索空间的减小过程（动图）
举一反三：二维矩阵搜索
Two Sum II 或许太过简单，并不需要用到搜索空间的知识。那么让我们来看看这个思想在另一个例题中的应用。
例题：LeetCode 240 - Search a 2D Matrix II[2]（Medium）
一个写一个高效的算法在矩阵中搜索目标值 target。
- 每行的元素从左到右升序排列
- 每列的元素从上到下升序排列
这道题目的特点是，二维矩阵本身就是搜索空间，所以我们不需要思考搜索空间的形状，直接进行搜索即可。看到有序的这个条件，我们很容易想到使用二分搜索。二分搜索的中间点，显然应该是矩阵的中心点：
二分搜索的中间点
不过仔细思考就会发现，根据矩阵的性质，这个中心点把矩阵分成的四个部分中，只有左上部分全部小于中心点，只有右下部分全部大于中心点。也就是说做一次比较最多只能削减 1/4 的搜索空间。更大的问题是，删除掉左上部分或者右下部分之后，剩余的形状不再是一个规则的矩形，就无法继续进行二分搜索了。
一次比较最多删除 1/4 的搜索空间
那么我们不妨换一种思路，不追求一次削减一半的搜索空间，而是像刚才的 Two Sum II 问题那样，一次削减一行或者一列。类比刚才的双指针解法，我们可以检查矩阵右上角的元素，即
matrix[0][7]
。
检查矩阵右上角的元素
如果
matrix[0][7]
小于目标值，由于矩阵每行是有序的，同一行所有的元素肯定都小于目标值，就可以排除一行的元素。
削减 i = 0 的一行搜索空间
而如果
matrix[0][7]
大于目标值，由于矩阵每列是有序的，同一列所有的元素一定都大于目标值，这又可以排除一列的元素。
削减 j = 7 的一列搜索空间
那么，我们每次都必定可以排除一行或一列的元素。经过
总结
从本文的例题可以看出，LeetCode 很多题目的答案很简单，但若想真正记住并举一反三，还是要理解题目背后的思想。Two Sum II 表面上是一个简单的双指针解法，但为了能想出这个解法，需要理解背后的搜索空间思想。
搜索空间的技巧需要在实际题目中灵活运用，本文中二维矩阵搜索例题的解法就是灵活运用了搜索空间思想。这里再列出一道和本题非常相关的题目，请仔细体会其中削减搜索空间的思想：
- 11. Container With Most Water[3]
参考资料
[1]
LeetCode 167 - Two Sum II - Input array is sorted: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
[2]
LeetCode 240 - Search a 2D Matrix II: https://leetcode.com/problems/search-a-2d-matrix-ii/
[3]
11. Container With Most Water: https://leetcode.com/problems/container-with-most-water/
欢迎关注我的公众号“五分钟学算法”，如果喜欢，麻烦点一下“