《力扣面试150题》题单拓展—

《力扣面试150题》题单拓展——双指针

1.基础知识

为什么双指针会正确？不会漏掉搜索空间

数组nums递增排序，假设共8个元素
假设由于搜索空间i < j的限制，只搜索右上角白色倒三角空间，一开始，我们检查右上方单元格(0,7)，即计算A[0] + A[7]，与 target 进行比较。如果不相等的话，则要么大于 target，要么小于 target

检查单元格 0, 7

假设此时 A[0] + A[7] 小于 target。这时候，我们应该去找和更大的两个数。由于 A[7] 已经是最大的数了，其他的数跟A[0]相加，和只会更小。也就是说 A[0] + A[6] 、A[0] + A[5]、……、A[0] + A[1] 也都小于 target，这些都是不合要求的解，可以一次排除。这相当于i=0 的情况全部被排除。对应用双指针解法的代码，就是 i++，对应于搜索空间，就是削减了一行的搜索空间，如下图所示。

削减空间

假设此时 A[1] + A[7]大于 target。这时候，我们应该去找和更小的两个数。由于 A[1] 已经是当前搜索空间最小的数了，其他的数跟 A[7] 相加的话，和只会更大。也就是说 A[1] + A[7] 、A[2] + A[7]、……、A[6] + A[7] 也都大于 target，这些都是不合要求的解，可以一次排除。这相当于 j=7 的情况全部被排除。对应用双指针解法的代码，就是 j--，对应于搜索空间，就是削减了一列的搜索空间，如下图所示

j缩减空间

2.缩减空间

240.搜索二维矩阵II

同样右上角开始，一列 / 一行的缩减空间

167.两数之和II-输入有序数组

基础知识图示例题

11.盛最多水的容器

之前一直还蒙，缩减空间后，豁然开朗

74.搜索二维矩阵

可以缩减空间，也可以去二分查找，先找到目标行就可以

3.双指针延伸

15.三数之和

i l r 三个指针的去重思想很棒，值得反复打磨

611.有效三角形的个数

固定哪个指针真的很有趣，一旦是最左边的，肯定做不出来

18.四数之和

固定前两个指针，转为了“三数之和”，可以借鉴三数之和的去重思路，注意j-i>1就是把j和i前面的隔出来，才能去重，不然本轮j的去重会和上轮的i重叠