《力扣面试150题》题单拓展——双指针
1.基础知识
为什么双指针会正确?不会漏掉搜索空间
- 数组
nums
递增排序,假设共8个元素 - 假设由于搜索空间
i < j
的限制,只搜索右上角白色倒三角空间,一开始,我们检查右上方单元格(0,7)
,即计算A[0] + A[7]
,与target
进行比较。如果不相等的话,则要么大于target
,要么小于target
- 假设此时
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--
,对应于搜索空间,就是削减了一列的搜索空间,如下图所示
2.缩减空间
同样右上角开始,一列 / 一行的缩减空间
基础知识图示例题
之前一直还蒙,缩减空间后,豁然开朗
可以缩减空间,也可以去二分查找,先找到目标行就可以
3.双指针延伸
i l r
三个指针的去重思想很棒,值得反复打磨
固定哪个指针真的很有趣,一旦是最左边的,肯定做不出来
固定前两个指针,转为了“三数之和”,可以借鉴三数之和的去重思路,注意
j-i>1
就是把j
和i
前面的隔出来,才能去重,不然本轮j
的去重会和上轮的i
重叠
4.常规扫描
标签:150,target,三数,力扣,搜索,空间,题单,指针 From: https://www.cnblogs.com/cyl018/p/17869584.html2824.统计和小于目标的下标对数目 难度分:1166
常规双指针扫描了,收集个数
两个条件分别控制
l r
指针,常规
找到前后max的min,就能计算当前可以存下的水,可以借助辅助的数组空间和纯正的双指针