双指针与滑动窗口

一句话：两个指针能把很多 O(n²) 的暴力枚举降到 O(n)，前提是移动指针时能保证不会漏掉正确答案——这个前提是否成立，取决于指针是”对撞”还是”同向”，而滑动窗口只是”同向双指针”的一种特殊形态。

对撞指针：利用单调性排除整段区间

15-三数之和、11-盛最多水的容器、167-两数之和II 都是排序后，从两端向中间逼近。核心洞察是：排序后数组具有单调性，每次比较 left/right 的和与目标值，可以直接排除掉”一整段不可能的区间”，而不是只排除一个元素——这正是复杂度从 O(n²) 降到 O(n) 的原因。

11-盛最多水的容器 的证明是这类题里最值得记住的：移动数值较小的那一侧指针，因为较大的一侧不动时，无论较小的一侧怎么移动，容器高度的瓶颈都不会超过较小值——所以移动较大的一侧绝不可能得到更优解，可以放心排除。

同向双指针：快慢指针原地覆盖

283-移动零、75-颜色分类（荷兰国旗问题）用两个同向指针分工：一个扫描（读），一个标记”已处理区域的边界”（写）。75 是三路指针的版本（75 用三个指针把数组分成”确定是0/待定/确定是2”三段，一次遍历完成三色排序），本质仍是数组与字符串里”读写指针分工”的模式，只是这里衡量的是”顺序”而非”去重”。

滑动窗口：同向双指针 + 窗口内状态

滑动窗口是同向双指针的特化：维护一个左右边界都只增不减的区间，区间需要满足某个约束（3-无重复字符的最长子串、76-最小覆盖子串、438/567-异位词/排列匹配）。模板固定：右指针扩张窗口、更新窗口内状态；当状态违反约束时收缩左指针，直到状态重新合法；每一步都尝试更新答案。

为什么左右指针都只增不减，复杂度还是 O(n)：因为左右指针总的移动步数之和不超过 2n（各自最多从头走到尾一次），不管中间来回收缩扩张多少次，均摊下来每个元素只被访问常数次——这也是一种摊还分析，参见摊还。

239-滑动窗口最大值 是滑动窗口和单调队列的组合：窗口本身用双指针维护，但”窗口内最大值”这个查询本身又是一个独立的子问题，解法见栈与队列。

易混：什么时候不能用双指针

双指针能生效的前提是”排除的区间确实不可能出现更优解”。如果数组无序且题目要求的关系不具有单调性（比如任意两数之和恰好等于某个数，但不允许排序改变原始下标顺序），对撞指针的证明就不成立，退化不能用——这时候应该回到哈希表的一次遍历查表模式，而不是硬套双指针模板。