第 34 章 两只手指——双指针
🏗️ 前情回顾：你已经用枚举和模拟解决了不少问题。但有些题目用两重循环会超时——比如"在一个有序数组中找两个数，使它们的和等于 target"。暴力做法 O(n²)，n 到 10⁵ 就炸了。有没有更快的办法？有！这就是双指针——用两个游走的"手指"在数据上跳舞，把复杂度砍到 O(n)。
🎯 本章目标
学完这一章，你能：
- 理解双指针的核心思想：两个指针协同移动，减少不必要的重复检查
- 掌握对撞指针（左右指针相向而行）
- 掌握快慢指针（一快一慢，用于判环/找中点）
- 掌握滑动窗口（区间伸缩，用于子数组问题）
- 用双指针优化从 O(n²) 到 O(n)，解决 A-B 数对、逛画展、两数之和等经典题
📖 故事引入
想象你有一条很长的绳子，上面串着很多珠子，每个珠子上写着一个数字（按从小到大排列）。你的任务是：找到两颗珠子，它们上面的数字之和等于 100。
你会怎么做？最笨的办法：左手拿一颗，右手把所有剩下的都摸一遍；然后左手换下一颗，右手再摸一遍……累死你，而且你摸了 n² 次。
聪明的方法：左手放在最左边（最小的数字），右手放在最右边（最大的数字）。计算两数之和：
- 如果和正好是 100 → 找到，收工！
- 如果和 < 100 → 左手往右移一格（增大总和）
- 如果和 > 100 → 右手往左移一格（减小总和）
左手指针只能往右走，右手只能往左走。每步排除一种不可能——两根手指各自走一遍，总共最多 O(n) 步就能找到答案或确认不存在。从 n² 到 n，这就是双指针的魔力。
🧱 知识讲解
34.1 双指针的核心思想
双指针（Two Pointers）不是一种数据结构，而是一种解题套路：用两个变量（"指针"）标记数组中的位置，根据某种条件协调移动它们，从而在一次遍历中解决需要两次遍历的问题。
📦 类比：双指针就像拉链——两个"拉链头"从两端（或同端不同速）出发，默契地走到一起。每次移动都不是盲目的——移动哪边、移多少，都由当前状态决定。
双指针有三种经典形态：
| 形态 | 描述 | 典型场景 |
|---|---|---|
| 对撞指针 | 一左一右，相向移动 | 有序数组两数之和 |
| 快慢指针 | 同向移动，速度不同 | 链表判环、找中点 |
| 滑动窗口 | 同向移动，维护区间 | 子数组/子串问题 |
34.2 对撞指针：两数之和
题目：给定一个升序排列的数组 a[0..n-1] 和一个 target，判断是否存在 i ≠ j 使得 a[i] + a[j] == target。若存在则输出这两个数。
bool twoSum(int a[], int n, int target) {
int l = 0, r = n - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) {
cout << a[l] << " " << a[r] << endl;
return true;
} else if (sum < target) {
l++; // 和太小 → 左指针右移，增大和
} else {
r--; // 和太大 → 右指针左移，减小和
}
}
return false;
}关键理解：为什么可以放心地 l++ 或 r--？因为数组是有序的。
- 如果
a[l] + a[r] < target，那么 a[l] 和任何在 r 左边的数之和只会更小。a[l] 已经没有任何希望了，所以l++。 - 同理，如果
a[l] + a[r] > target，a[r] 和任何在 l 右边的数之和只会更大。a[r] 已经没戏了，所以r--。
⚠️ 前提：对撞指针要求数组有序。如果无序，可以先用
sort排序再双指针——总复杂度 O(n log n)，依然优于 O(n²)。
34.3 快慢指针：判环与找中点
快慢指针在链表中最常见（你后面会详细学链表），但思想同样可以用在数组上。
找中点的思想：慢指针每次走一步，快指针每次走两步。当快指针走到末尾时，慢指针刚好在中间。
int findMiddle(int a[], int n) {
int slow = 0, fast = 0;
while (fast + 1 < n && fast + 2 < n) {
slow++;
fast += 2;
}
return a[slow]; // 中位数（偏左）
}📦 类比：操场跑步——你跑得比你朋友快一倍。当你跑完一圈追上他的时候，他刚好跑了半圈。这就是快慢指针的几何直觉。
34.4 滑动窗口：A-B 数对
滑动窗口的核心是维护一个可变区间 [l, r]，窗口大小和位置根据条件动态调整。
题目（NOIP 2007 普及组简化变体）：「A-B 数对」——给定 n 个正整数和一个数 C，求满足 A - B = C 的数对 (A, B) 的个数。
暴力：枚举 B，然后找 A = B + C，用二分查找即 O(n log n)。但双指针能做得更优雅。
双指针思路：排序后，用两个指针 l 和 r 分别维护"第一个等于 B+C 的位置"和"最后一个等于 B+C 的位置"，对于每个 B，(r - l) 就是 A 的个数。
long long countPairs(int a[], int n, int C) {
sort(a, a + n);
long long ans = 0;
int l = 0, r = 0;
for (int i = 0; i < n; i++) { // 枚举 B = a[i]
while (l < n && a[l] < a[i] + C) l++;
while (r < n && a[r] <= a[i] + C) r++;
ans += (r - l);
}
return ans;
}34.5 滑动窗口：逛画展
题目（简化版）：博物馆有 n 幅画排成一排，每幅画有一个画家编号（1~m）。你需要找一个最短的连续区间，使得这个区间里包含了所有 m 位画家的画各至少一幅。
暴力 O(n²)：枚举每个起点，向右扩展直到收集全所有画家。
滑动窗口优化：维护窗口 [l, r)，用一个 cnt[] 数组记录窗口内每种画家画的数量。当窗口还没集齐时，r++（扩张）；当窗口已集齐时，尝试 l++（收缩），更新最短长度。
int solve(int a[], int n, int m) {
int cnt[2005] = {0}; // 记录窗口内每种画的数量
int collected = 0; // 当前已收集的画种数
int ans = n + 1;
int l = 0;
for (int r = 0; r < n; r++) {
if (cnt[a[r]] == 0) collected++;
cnt[a[r]]++;
while (collected == m) { // 集齐了，尝试收缩左端
ans = min(ans, r - l + 1);
cnt[a[l]]--;
if (cnt[a[l]] == 0) collected--;
l++;
}
}
return ans;
}滑动窗口的精髓：两个指针都只向右移动，每个元素被 l 和 r 各访问常数次，总复杂度 O(n)。
📦 类比：滑动窗口像一条毛毛虫——头向前探（r++），身体跟上（l++）。身体永远不会超过头，大家都只往前走，从不后退。
34.6 双指针复杂度对比
| 问题 | 暴力 | 双指针 |
|---|---|---|
| 有序数组两数之和 | O(n²) | O(n) |
| A-B 数对 | O(n²) | O(n)（排序 O(n log n)） |
| 最短覆盖区间 | O(n²) | O(n) |
| 最长无重复子串 | O(n²) | O(n) |
💡 双指针为什么快？因为暴力枚举做了大量重复检查。比如两数之和中，暴力会检查
(a[0], a[1]), (a[0], a[2]), ...共 O(n²) 对，但有序性告诉我们绝大多数对根本不需要看。双指针每次移动都"排除了一批不可能"，从不回头。
✋ 动手试试
试试 1：写对撞指针版"两数之和"，外加主函数输入测试。试几组数据验证正确性。
试试 2：用快慢指针找出一个数组的中位数下标（不排序，只是找位置）。
试试 3：用滑动窗口找出一个字符串中的最长无重复字符子串的长度。
⚠️ 容易犯的错
错 1：对撞指针数组没排序
❌ 数组是 {3, 1, 4, 1, 5}，直接双指针 → 结果错误。
✅ 先 sort(a, a+n); 再双指针（或者用哈希表等其他方法）。
错 2：滑动窗口的 while 条件写成 if
❌ if (collected == m) { ans = min(ans, r-l+1); l++; } ——只收缩一次，可能错过更短的答案。
✅ 用 while (collected == m) 持续收缩直到不再满足条件。
错 3：指针越界
❌ 对撞指针写成 while (l <= r)，在 l == r 时同一个元素用了两次。
✅ 题目要求两个不同元素时，条件应为 while (l < r)。
错 4：滑动窗口中忘记更新 collected
❌ cnt[a[l]]--; l++; ——忘了检查 cnt[a[l]] 变成 0 时 collected--。
✅ 先减计数，若归零则 collected--。
📝 练习
基础题
1. 选择题
（1）对撞指针适用于什么情况？
A. 无序数组 B. 有序数组 C. 链表 D. 树
（2）滑动窗口中，右指针 r 的作用通常是：
A. 收缩窗口 B. 扩张窗口 C. 保持窗口大小不变 D. 重置窗口
（3）快慢指针中快指针的速度通常是慢指针的：
A. 1.5 倍 B. 2 倍 C. 3 倍 D. 任意倍
2. 填空题
（1）对撞指针中 l++ 的依据是 ____。
（2）滑动窗口的总复杂度是 O(____) ，因为左右指针各自最多移动 ____ 次。
（3）有序数组两数之和问题用暴力是 O(____)，用双指针是 O(____)。
提高题
3. 编程题 — 三数之和
给定有序数组和 target，找出所有满足 a[i] + a[j] + a[k] == target 的三元组（不重复）。提示：固定一个数，剩下的用对撞指针。
4. 编程题 — 最长连续不重复子序列
输入 n 个整数，输出最长连续子序列的长度，该子序列没有重复元素。
挑战题
5. 编程题 — 盛水最多的容器
给定 n 个非负整数 a[0..n-1] 表示挡板高度，每个挡板间距为 1。找出两个挡板，使它们与 x 轴围成的容器能装最多的水。用对撞指针 O(n) 求解。
6. 编程题 — 最小覆盖子串
输入两个字符串 S 和 T，在 S 中找出包含 T 所有字母的最短子串。如果不存在则输出空串。
🧠 本章小结
双指针 = 两个变量协同游走，省掉重复检查
三种形态：
对撞指针： l→ ←r 有序数组，相向而行
快慢指针： s→ f→→ 一快一慢，判环找中点
滑动窗口： [l..r)→ 区间可伸缩，子数组/子串问题
复杂度跃迁：
O(n²) → O(n)（或 O(n log n) 含排序）
核心思维：
每次移动都"排除一批不可能"，只走一遍
前提通常是数组有序或满足单调性📝 配套练习
共7题。对撞指针2题+滑动窗口4题+综合1题——双指针的三种形态都练到。。★核心（课堂必做） ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | luogu-P1102 | https://hydro.ac/p/luogu-P1102 | 对撞指针、A-B数对 |
| ◆ 拓展 | luogu-P1638 | https://hydro.ac/p/luogu-P1638 | 滑动窗口、最短区间 |
| ◆ 拓展 | luogu-P1115 | https://hydro.ac/p/luogu-P1115 | 双指针/前缀和、最大子段和 |
| ◆ 拓展 | luogu-P1381 | https://hydro.ac/p/luogu-P1381 | 滑动窗口、单词背诵 |
| ◆ 拓展 | luogu-P3029 | https://hydro.ac/p/luogu-P3029 | 对撞指针、牛 |
| ◆ 拓展 | luogu-P3143 | https://hydro.ac/p/luogu-P3143 | 双指针+排序 |
| ◆ 拓展 | luogu-P5745 | https://hydro.ac/p/luogu-P5745 | 滑动窗口、子数组和 |
💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。
配套练习
共7题。对撞指针2题+滑动窗口4题+综合1题——双指针的三种形态都练到。★核心（课堂必做） · ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | luogu-P1102 | https://hydro.ac/p/luogu-P1102 | 对撞指针、A-B数对 |
| ◆ 拓展 | luogu-P1638 | https://hydro.ac/p/luogu-P1638 | 滑动窗口、最短区间 |
| ◆ 拓展 | luogu-P1115 | https://hydro.ac/p/luogu-P1115 | 双指针/前缀和、最大子段和 |
| ◆ 拓展 | luogu-P1381 | https://hydro.ac/p/luogu-P1381 | 滑动窗口、单词背诵 |
| ◆ 拓展 | luogu-P3029 | https://hydro.ac/p/luogu-P3029 | 对撞指针、牛 |
| ◆ 拓展 | luogu-P3143 | https://hydro.ac/p/luogu-P3143 | 双指针+排序 |
| ◆ 拓展 | luogu-P5745 | https://hydro.ac/p/luogu-P5745 | 滑动窗口、子数组和 |
练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。
自查清单：
- [ ] 我能写出对撞指针解决有序数组两数之和
- [ ] 我理解滑动窗口的"扩张-收缩"循环模式
- [ ] 我会用滑动窗口解决最短覆盖区间问题
- [ ] 我知道双指针为什么是 O(n) 而不是 O(n²)
- [ ] 我能在代码中正确维护滑动窗口的计数变量
- [ ] 我能把 A-B 数对问题转化为双指针解法
🚀 下章预告：双指针帮你省掉了重复计算——但还有另一类重复计算：同一个区间和被求了无数次。下一章《预制计算——前缀和与差分》，你学会"预处理一次，查询 O(1)"的神技——区间求和？随手就来！📊