如果一道关于数对、子数组或子串的题目在 O(n²) 下超时，双指针滑动窗口模式通常就是你要找的解法。
这两个思想是竞赛程序员早期就该学会的最有价值技巧之一。它们看似简单，却能把一大类暴力解法转化为简洁的线性时间代码。在 BIAA 的竞赛编程项目中，我们把它们放在一起讲授，因为它们共享一个核心洞见：与其每次都从头检查每一个区间，不如让两个下标在数据中移动，并复用你已经做过的工作。
双指针技巧到底在做什么
双指针技巧使用两个下标遍历一个数组或字符串，用单次扫描取代嵌套循环。常见的移动模式有两种：
- 对撞指针：一个从左端开始，一个从右端开始，二者相向而行。这是诸如有序数组上的 Two Sum 或盛最多水的容器这类问题的标准做法——你比较两个端点的值，然后决定推进哪个指针。
- 同向指针：两者都从左向右移动，往往速度不同，一个落后于另一个。它适用于诸如原地删除有序数组中的重复元素，或者划分（partition）这类问题。
收益是实打实的：许多需要嵌套循环 O(n²) 的问题会降到 O(n)，因为每个指针最多只穿过数组一次。需要注意的是，对撞型双指针通常要求数据先排序，所以一旦把排序也算进来，真正的代价往往是 O(n log n)。
滑动窗口：双指针的变体
滑动窗口是双指针的一种特例：两个下标朝同一方向移动，而你真正关心的答案是它们之间的那段区域。把它想象成一只在数组上爬行的尺蠖：右指针扩展窗口以纳入新元素，当某个条件被破坏时，左指针收缩窗口。随着窗口滑动，你维护一个动态的汇总信息，比如一个和或一个字符计数，而不是从头重新计算。
有两种值得牢记的形态：
- 定长窗口：窗口长度是给定的且保持不变。你每次滑动一步，加入新元素并移除旧元素。经典例子：任意长度为 k 的连续子数组的最大和。
- 变长窗口：窗口为满足某个约束而伸缩。经典例子：无重复字符的最长子串——你不断扩展直到遇到重复字符，然后从左侧收缩。
何时选用哪种模式
有几个可靠的信号能帮你在赛场压力下快速判断：
- 诸如「数对」「有序」「交换」之类的词往往指向对撞型双指针。
- 诸如「连续子数组」「子串」「窗口」或「至多 / 恰好 K 个」之类的词几乎总是意味着滑动窗口。
- 如果数组未排序且顺序无关紧要，考虑先排序，或把该技巧与前缀和搭配使用。
有一个重要的注意点：基础的滑动窗口假设扩展窗口只会让某个量朝一个方向变化（它单调地保持有效，或单调地保持无效）。比如，存在负数时，和会随着窗口增大而不再单调，因此朴素的窗口可能会失效。在这些情况下，学员要学会改用前缀和结合二分查找或其他工具。
精通不是背下两个模板。它是在几秒之内识别出一道题奖励的是哪种结构，然后信任那次线性扫描。
在官方的 USACO 赛道上，双指针是 Silver 级别的核心主题，而滑动窗口在 Gold 级别又会再次出现，所以尽早熟练能让你在多个赛季中持续获益。内化这一模式的最好办法是刻意练习：先做一道定长窗口的题，再做一道变长窗口的题，然后做一道对撞指针的数对题，并写下是哪个信号告诉你该用哪种方法。
如果你的孩子已经准备好，从理解这些模式迈向在真实赛场约束下加以运用，我们的教练会为他规划一条结构化、逐题推进的路径，迈向奥赛级别的熟练度。欢迎了解 BIAA 的竞赛编程项目，立即开始。