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

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

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

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};
}

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
两个指针从两头向中间移动
LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
两个指针在中间相遇

很多题解都只给出了这样一个答案,仿佛道理是不证自明的。但事实上,这个解法并不是能让人一眼就看懂。我第一次看到这道题的答案时,把这个解法叫做 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 的下标 。以  为例,这时候全部的搜索空间是:

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
下标 i, j 的搜索空间

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

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
检查单元格 0, 7

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
排除 i = 0 的全部解

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
检查单元格 1, 7

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
排除 j = 7 的全部解

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
搜索空间的减小过程(动图)

举一反三:二维矩阵搜索

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

例题:LeetCode 240 – Search a 2D Matrix II[2](Medium)

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

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

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

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
二分搜索的中间点

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
一次比较最多删除 1/4 的搜索空间

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
检查矩阵右上角的元素

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
削减 i = 0 的一行搜索空间

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

LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间
削减 j = 7 的一列搜索空间

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

总结

从本文的例题可以看出,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/


推荐阅读

•   60 个相见恨晚的神器工具•   一线互联网公司技术面试的流程以及注意事项•   自学编程的八大误区!克服它!•   新手如何有效的刷算法题(LeetCode)•   10款VS Code插件神器,第7款超级实用!•   在拼多多上班,是一种什么样的体验?我tm心态崩了呀!•   写给小白,从零开始拥有一个酷炫上线的网站!


欢迎关注我的公众号“五分钟学算法”,如果喜欢,麻烦点一下“在看”~

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

原文始发于微信公众号(五分钟学算法):LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » LeetCode 例题精讲 | 04 用双指针解 Two Sum:缩减搜索空间

我还会在以下平台发布内容

GitHub 哔哩哔哩