Two Pointers

核心思路：利用单调性或有序性，让指针不走回头路，把很多原本 O(n^2) 的枚举降到 O(n) 或 O(n log n)。

First Question

双指针不是一个模板，而是一类“两个边界一起维护状态”的思路。遇到题目时先问：

1. 两根指针各代表什么边界？
2. 指针移动后，区间 / 数对 / 状态的性质会不会单调变化？
3. 是否能保证每个元素最多被某个指针扫过有限次？

如果这三点成立，双指针通常就值得优先考虑。

Four Main Directions

• 同向: 一前一后，常见于滑动窗口、快慢指针、数组去重
• 相向: 一头一尾，常见于 2Sum、回文、partition
• 背向: 从中心往两边扩散，常见于回文串
• 平行: 两个有序序列同步推进，常见于 merge、匹配、对齐

By Problem Type

1. 同向双指针

特点：右指针通常每轮前进一次，左指针只在违反条件时收缩。

典型信号：

• 子数组 / 子字符串
• 固定或可变窗口
• 去重
• 快慢指针

for (int left = 0, right = 0; right < n; right++) {
    // add nums[right]
    while (left <= right && invalid(left, right)) {
        // remove nums[left]
        left++;
    }
    // update answer
}

2. 相向双指针

特点：两根指针从两端往中间靠拢，根据当前比较结果舍弃一整块不可能答案。

典型信号：

• 有序数组上的 2Sum / 3Sum
• 回文判断
• partition / quick sort
• 雨水、容器、配对问题

3. 背向双指针

特点：从中间某个中心出发向外扩展。

典型信号：

• 最长回文子串
• 中心扩散类问题

4. 平行双指针

特点：两个有序序列或两个流同时向前推进。

典型信号：

• merge 两个有序数组 / 链表
• 匹配两个序列
• Z 型 / 对角线类遍历

Common Patterns

• 滑动窗口: 窗口内部始终维护一个性质
• 快慢指针: 一个一步，一个两步，常用于链表
• 有序数对: 利用排序后单调关系剪枝
• 去重: 通过跳过重复段避免重复答案

When Not to Use

• 状态不具备单调性，移动一个指针不能稳定缩小搜索空间
• 需要回头反复试探，本质更像 DFS / DP
• 题目不是区间 / 数对 / 路径边界，而是图或树结构

Related Docs

• Window
• Parallel
• Opposite
• K Pointers