[算法学习]模板-双指针(对撞指针和滑动窗口)

---

双指针算法系统复盘：从暴力枚举到区间控制

在系统学习双指针之前，我对它的理解只是：

“两个指针一起动就叫双指针。”

但真正深入后发现，它其实是一种优化枚举顺序的思想。

双指针的本质是：

用两个变量控制一个区间，
利用单调性或区间性质，
把 O(n²) 的枚举压缩成 O(n)。

理解它的关键，不是背模板，而是理解：

• 我们在消灭什么重复？
• 为什么指针不会回退？
• 为什么不会漏解？

---

一、为什么双指针能优化？

我们先看一个典型暴力结构：

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // 判断区间 [i, j]
    }
}

这个结构做了什么？

• 枚举所有区间
• 一共有 O(n²) 个

但很多题目中：

• 区间具有单调性
• 或者区间的某种性质可以“递推维护”

一旦区间性质是“可递推的”，我们就可以：

不再重复枚举右端点

于是双指针就诞生了。

---

二、双指针分类

双指针根据移动方式分为：

1. 对撞指针
2. 滑动窗口

它们解决问题的方式不同。

---

第一部分：对撞指针

---

1️⃣ 思想核心

两个指针分别在区间两端：

left →        ← right

通过移动其中一个指针，让区间不断收缩。

关键前提：

必须有单调性

---

2️⃣ 从暴力到优化：完整推理过程

例子：有序数组中找两个数等于 target。

暴力：

for (i)
    for (j)

O(n²)

---

为什么可以优化？

因为数组是有序的。

假设：

nums[left] + nums[right] > target

说明什么？

• 右侧元素太大
• 即使 left++，和只会更大
• 所以必须 right–

我们一次性排除了：

所有以当前 right 为右端点的组合

这就是关键：

每一步都排除一整片区域。

---

3️⃣ 数学本质

对撞指针本质是：

利用单调性剪枝

剪枝条件：

• 当右端点减小，区间和减小
• 当左端点增大，区间和增大

如果没有这种单调性，对撞指针无法成立。

---

4️⃣ 标准模板

int left = 0;
int right = n - 1;

while (left < right) {

    int sum = nums[left] + nums[right];

    if (sum == target) {
        return true;
    }
    else if (sum > target) {
        right--;
    }
    else {
        left++;
    }
}

---

5️⃣ 对撞指针的判断条件

可以用对撞指针的必要条件：

• 数组有序
• 或结果与区间边界呈单调关系
• 移动一个指针后，答案不会被漏掉

---

6️⃣ 典型问题拓展

✔ 判断回文

左右比较即可。

✔ 三数之和

固定一个数后，对剩余部分做对撞指针。

✔ 盛水容器

移动短板，因为：

面积由短板决定

---

第二部分：滑动窗口

---

如果说对撞指针是“从两端收缩”，

那么滑动窗口是：

动态维护一个合法区间。

---

1️⃣ 核心结构

left → → → → 
        right →

两个指针都向右移动。

---

2️⃣ 从暴力到优化推理

暴力枚举子数组：

for (left)
    for (right)

O(n²)

但很多问题满足：

• 区间具有某种“可维护状态”
• 加入一个元素可以 O(1) 更新状态
• 移除一个元素也可以 O(1) 更新状态

例如：

• 区间和
• 区间字符频率
• 区间是否包含重复

只要满足：

区间状态可递推维护

就可以使用滑动窗口。

---

3️⃣ 为什么是 O(n)？

因为：

• right 只走 n 次
• left 只走 n 次

每个元素：

• 进窗口一次
• 出窗口一次

总操作 O(2n)

---

4️⃣ 通用模板（必须掌握）

int left = 0;

for (int right = 0; right < n; right++) {

    // 1. 扩张窗口
    加入 nums[right]

    // 2. 当窗口不合法时
    while (不满足条件) {
        移除 nums[left]
        left++;
    }

    // 3. 更新答案
}

结构必须是：

先扩张
再收缩
最后更新

---

5️⃣ 经典问题分析

---

🔹 最长无重复子串

维护：

• 一个计数数组

当出现重复：

while (重复) {
    count[s[left]]--;
    left++;
}

---

🔹 最小覆盖子串

维护：

• 目标字符数量
• 当前匹配数量

当满足条件：

• 更新答案
• 尝试收缩

---

🔹 长度最小子数组（和 ≥ target）

维护：

• 当前区间和

当 sum ≥ target：

• 更新答案
• 左移

---

三、对撞 vs 滑动窗口 本质区别

方面	对撞指针	滑动窗口
指针方向	两端向中间	同向
核心依赖	单调性	区间状态可维护
适用问题	有序数组	子数组问题
典型目标	找组合	找连续区间

---

四、如何判断是否能用双指针？

问自己三件事：

1️⃣ 是连续区间问题吗？
→ 是，优先考虑滑动窗口

2️⃣ 数组是否有序？
→ 是，优先考虑对撞指针

3️⃣ 区间状态能 O(1) 维护吗？
→ 是，可以滑动窗口

---

五、双指针真正的本质

双指针不是“两个指针”。

本质是：

用区间状态替代重复枚举

暴力是：

• 每个 left 对应枚举所有 right

双指针是：

• right 不回退
• left 不回退
• 每个元素只处理常数次

这是一种：

结构优化，而不是技巧。

---

六、我对双指针的阶段性理解

最开始：

• 看到区间就想到双指针

后来发现：

• 不是所有区间问题都能用

真正理解后：

• 核心在于“单调性”和“状态可维护性”

---

七、总结

对撞指针：

用单调性剪枝

滑动窗口：

用合法区间消灭重复枚举

两者共同核心：

不回退

---