双指针扫描
双指针扫描
- 用于解决一类
基于子段的统计问题 - 子段：数组中连续的一段（下标范围可以用一个闭区间来表示）
- 这类题目的朴素做法都是两重循环的枚举，枚举左端点 l l l 、右端点 r （ l ≤ r ） r（l \leq r） r（l≤r）
- 优化手法都是找到枚举中的冗余部分，将其去除
- 优化策略
固定右端点，看左端点的取值范围- 例如左端点的取值范围是一个前缀，可以用 “前缀和” 等算法维护前缀信息
移动一个端点，看另一个端点的变化情况- 例如一个端点跟随另一个端点单调移动，像一个 “滑动窗口”
- 此时可以考虑 “双指针扫描”
总结
- 区间减法性质
- 指的是 [ l , r ] [l, r] [l,r] 的信息可以由 [ 1 , r ] 和 [ 1 , l − 1 ] [1, r] 和 [1, l - 1] [1,r]和[1,l−1] 导出
- 满足区间减法，用
前缀和
- 维护的信息是关于一个点的用
双指针扫描 - 维护的信息是一整个候选集合（多个点）的用
单调队列
LeetCode 练习题
- 167. 两数之和 II - 输入有序数组
- 1. 两数之和
- 15. 三数之和
- 11. 盛最多水的容器