Skip to content

双指针

包括同向双指针和相向双指针

相向双指针

用于统计某种性质

构造某种不等式约束,使得left左移和right右移贡献相反(或者一边移动贡献为0),从而得出O(n)枚举策略

  • 相向双指针常见套路: 从数组中选2个数,满足...关系(可以是不等关系) 如果选>2个数,一般暴力枚举直到剩下两个数字(3数之和,4数之和) 去重时应该从定义出发思考

同向双指针(滑动窗口)

利用决策单调性,寻找满足某种条件的子数组/子串

本质:枚举右端点,优化左端点的枚举,利用题目性质构造出某种贡献约束(包括不等式关系等) 将左指针由O(n)优化到O(1)获取信息 (保存上一次的某个端点枚举结果,利用约束省去无用的枚举部分)

不知道怎么思考时:先思考暴力枚举,然后思考如何利用保存上一次的某个端点枚举结果,省去无用的枚举部分

常见套路:

  • 对一个数组只能去头和去尾操作可以转化为维护中间的滑窗
  • 贡献也可维护数组外部的计算
  • 明确上一次滑窗结果是符合滑窗条件的(或者临界符合)

网站基于vitepress主题open17💙