双指针
包括同向双指针和相向双指针
相向双指针
用于统计某种性质
构造某种不等式约束,使得left左移和right右移贡献相反(或者一边移动贡献为0),从而得出O(n)枚举策略
- 相向双指针常见套路: 从数组中选2个数,满足...关系(可以是不等关系) 如果选>2个数,一般暴力枚举直到剩下两个数字(3数之和,4数之和) 去重时应该从定义出发思考
同向双指针(滑动窗口)
利用决策单调性,寻找满足某种条件的子数组/子串
本质:枚举右端点,优化左端点的枚举,利用题目性质构造出某种贡献约束(包括不等式关系等) 将左指针由O(n)优化到O(1)获取信息 (保存上一次的某个端点枚举结果,利用约束省去无用的枚举部分)
不知道怎么思考时:先思考暴力枚举,然后思考如何利用保存上一次的某个端点枚举结果,省去无用的枚举部分
常见套路:
- 对一个数组只能去头和去尾操作可以转化为维护中间的滑窗
- 贡献也可维护数组外部的计算
- 明确上一次滑窗结果是符合滑窗条件的(或者临界符合)