第 3.4 章：双指针与滑动窗口
📝 前置条件： 你应该熟悉数组、向量和
std::sort（第 2.3–3.3 章）。经典双指针方法需要已排序的数组。
双指针和滑动窗口是竞赛编程中最优雅的技巧之一。它们通过利用单调性将朴素 O(N²) 解法转化为 O(N)：当一个指针向前移动时，另一个指针无需回头。
3.4.1 双指针技术
核心思想：在有序数组中维护两个下标 left 和 right，根据当前和/窗口大小将它们相向（或同向）移动。
使用场景：
- 在有序数组中找满足给定和的对/三元组
- 检查有序数组中是否存在满足特定关系的两个元素
- 「若能用大小 k 的窗口完成 X，则用大小 k-1 的窗口也能完成」的问题
上图展示两个指针如何向中间收拢，每步都从待考虑的对中消除整行/整列。
滑动窗口变体让两个指针同向移动。满足条件时，从左侧收缩以找到最小窗口：
题目：找出所有和为目标值的对
朴素 O(N²) 做法：
// O(N²)：检查每一对
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
cout << arr[i] << " + " << arr[j] << "\n";
}
}
}
双指针 O(N) 做法（需要排序）：
📄 C++ 完整代码
// 双指针 — 排序 O(N log N) + 搜索 O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, target;
cin >> n >> target;
vector<int> arr(n);
for (int &x : arr) cin >> x;
sort(arr.begin(), arr.end()); // 必须先排序
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
cout << arr[left] << " + " << arr[right] << " = " << target << "\n";
left++;
right--; // 同时移动两个指针
} else if (sum < target) {
left++; // 和太小：左指针右移（增大和）
} else {
right--; // 和太大：右指针左移（减小和）
}
}
return 0;
}
为什么这样有效？
核心思路： 排序后，若 arr[left] + arr[right] < target，则没有比 arr[right] 更小的元素能与 arr[left] 配对达到 target。所以安全地右移 left。
类似地，若和太大，没有比 arr[left] 更大的元素能与 arr[right] 配对达到 target。所以安全地左移 right。
每步至少消除一个元素 → 总计 O(N) 步。
完整追踪
数组 = [1, 2, 3, 4, 5, 6, 7, 8]，target = 9：
📄 数组 = [1, 2, 3, 4, 5, 6, 7, 8]，target = 9：
状态：left=0(1), right=7(8)
和 = 1+8 = 9 ✓ → 打印 (1,8)，left++，right--
状态：left=1(2), right=6(7)
和 = 2+7 = 9 ✓ → 打印 (2,7)，left++，right--
状态：left=2(3), right=5(6)
和 = 3+6 = 9 ✓ → 打印 (3,6)，left++，right--
状态：left=3(4), right=4(5)
和 = 4+5 = 9 ✓ → 打印 (4,5)，left++，right--
状态：left=4, right=3 → left >= right，停止
所有对：(1,8)，(2,7)，(3,6)，(4,5)
三数之和扩展
找和为目标值的三元组：固定一个元素，对剩余两个用双指针。
📄 找和为目标值的三元组：固定一个元素，对剩余两个用双指针。
// O(N²) — 远优于 O(N³) 暴力
sort(arr.begin(), arr.end());
for (int i = 0; i < n - 2; i++) {
int left = i + 1, right = n - 1;
while (left < right) {
int sum = arr[i] + arr[left] + arr[right];
if (sum == target) {
cout << arr[i] << " " << arr[left] << " " << arr[right] << "\n";
left++; right--;
} else if (sum < target) left++;
else right--;
}
}
3.4.2 滑动窗口——固定大小
固定大小 K 的滑动窗口在数组上滑动，维护一个运行聚合值（和、最大值、不同值计数等）。
题目： 找任意大小为 K 的连续子数组的最大和。
数组：[2, 1, 5, 1, 3, 2]，K=3
窗口：[2,1,5]=8，[1,5,1]=7，[5,1,3]=9，[1,3,2]=6
答案：9
朴素 O(NK)： 对每个窗口从头重新计算和。
滑动窗口 O(N)： 加上进入窗口的新元素，减去离开窗口的旧元素。
📄 C++ 完整代码
// 固定大小滑动窗口 — O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<int> arr(n);
for (int &x : arr) cin >> x;
// 计算第一个窗口的和
long long windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
long long maxSum = windowSum;
// 滑动窗口：加 arr[i]，减 arr[i-k]
for (int i = k; i < n; i++) {
windowSum += arr[i]; // 新元素进入窗口
windowSum -= arr[i - k]; // 旧元素离开窗口
maxSum = max(maxSum, windowSum);
}
cout << maxSum << "\n";
return 0;
}
对 [2, 1, 5, 1, 3, 2], K=3 的追踪：
初始窗口 [2,1,5]：sum=8，max=8
i=3：加 1，减 2 → sum=7，max=8
i=4：加 3，减 1 → sum=9，max=9
i=5：加 2，减 5 → sum=6，max=9
答案：9 ✓
3.4.3 滑动窗口——可变大小
最强大的变体：窗口在需要时扩大，违反约束时收缩。
题目： 找和 ≥ target 的最短连续子数组。
📄 C++ 完整代码
// 可变大小窗口 — O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, target;
cin >> n >> target;
vector<int> arr(n);
for (int &x : arr) cin >> x;
int left = 0;
long long windowSum = 0;
int minLen = INT_MAX;
for (int right = 0; right < n; right++) {
windowSum += arr[right]; // 扩张：加入右端元素
// 满足约束时从左收缩
while (windowSum >= target) {
minLen = min(minLen, right - left + 1);
windowSum -= arr[left];
left++; // 收缩：移除左端元素
}
}
if (minLen == INT_MAX) cout << 0 << "\n"; // 不存在这样的子数组
else cout << minLen << "\n";
return 0;
}
为什么是 O(N)？ 每个元素被加入一次（right 经过时），最多被移除一次（left 经过时）。总操作：O(2N) = O(N)。
题目：最多 K 个不同值的最长子数组
📄 查看代码：题目：最多 K 个不同值的最长子数组
// 可变窗口：最多 K 个不同值的最长子数组
int left = 0, maxLen = 0;
map<int, int> freq; // 窗口内每个值的频率
for (int right = 0; right < n; right++) {
freq[arr[right]]++;
// 有 > k 个不同值时收缩
while ((int)freq.size() > k) {
freq[arr[left]]--;
if (freq[arr[left]] == 0) freq.erase(arr[left]);
left++;
}
maxLen = max(maxLen, right - left + 1);
}
cout << maxLen << "\n";
3.4.4 USACO 示例：最长满足条件的子数组
题目： 给定整数数组，找所有元素 ≥ K 的最长连续子数组。
// 双指针：所有元素 >= K 的最长连续子数组
int left = 0, maxLen = 0;
for (int right = 0; right < n; right++) {
if (arr[right] < K) {
left = right + 1; // 重置窗口：当前元素违反约束
} else {
maxLen = max(maxLen, right - left + 1);
}
}
3.4.5 USACO 真题训练：窗口、匹配与单调移动
双指针的本质是「指针不回头」。在 USACO 中常见两类题：
| 模式 | 题面信号 | 指针含义 |
|---|---|---|
| 排序后滑动窗口 | 最大集合，任意两者差距不超过 K | 窗口左右端点 |
| 区间匹配 | 每个资源只能用一次，最大匹配数量 | 当前资源 + 可匹配候选集合 |
真题 1：Diamond Collector（USACO 2016 US Open Silver）— 排序后维护合法窗口
题目链接： USACO 2016 US Open Silver P2: Diamond Collector
对应模式： 排序 + 滑动窗口 + 前后缀最优
难度定位： Silver 中等
题干解读
有 N 颗钻石，每颗有一个大小。一个展示柜中任意两颗钻石大小差不能超过 K。你有两个展示柜，求最多能展示多少颗钻石。
关键条件：
- 每个柜子对应排序数组中的一个连续窗口。
- 两个柜子不能共用钻石。
- 需要选两个不重叠窗口，使总长度最大。
思路分析
排序后，对每个左端点 left，用右指针扩张到最大 right，满足：
size[right] - size[left] <= K
得到从 left 开始的最大合法窗口长度。然后用后缀最大值 bestFrom[i] 表示从位置 i 之后能选到的最大窗口。枚举第一个柜子的左端点，第二个柜子从第一个窗口右端之后开始。
CPP 完整代码
✅ 完整代码：Diamond Collector
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// USACO 官方文件 I/O 可按需打开：
// freopen("diamond.in", "r", stdin);
// freopen("diamond.out", "w", stdout);
int n, k;
cin >> n >> k;
vector<int> diamond(n);
for (int &x : diamond) cin >> x;
sort(diamond.begin(), diamond.end());
vector<int> length(n), endAt(n);
int right = 0;
for (int left = 0; left < n; left++) {
while (right < n && diamond[right] - diamond[left] <= k) {
right++;
}
length[left] = right - left;
endAt[left] = right; // 第二个柜子必须从 right 或之后开始
}
vector<int> bestFrom(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
bestFrom[i] = max(bestFrom[i + 1], length[i]);
}
int answer = 0;
for (int first = 0; first < n; first++) {
answer = max(answer, length[first] + bestFrom[endAt[first]]);
}
cout << answer << "\n";
return 0;
}
复杂度： 排序 O(N log N)，滑动窗口和后缀数组 O(N)，空间 O(N)。
易错点提醒
- 右指针回退。 滑动窗口的关键是
right只增不减，否则退化成O(N²)。 - 两个柜子重叠。 第二个柜子必须从第一个窗口结束位置
endAt[first]之后选。 - 只找一个最大窗口。 题目有两个展示柜，需要组合两个不重叠窗口。
- 没有排序。 合法窗口只在排序后才是连续区间。
拓展思考
如果展示柜数量从 2 变成 M，就变成「选 M 个不重叠窗口最大化总长度」的 DP：dp[i][j] 表示从第 i 个位置开始，用 j 个柜子的最大展示数量。
真题 2：Why Did the Cow Cross the Road（USACO 2017 February Silver）— 区间匹配的贪心
题目链接： USACO 2017 February Silver P1: Why Did the Cow Cross the Road
对应模式： 排序 + 贪心匹配 + 最小堆
难度定位： Silver 中等
题干解读
有若干只鸡，每只鸡在一个具体时间 T 可以帮忙；有若干头牛，每头牛只能在时间区间 [A,B] 内过马路。一只鸡最多帮一头牛，一头牛也最多被一只鸡帮助，求最大匹配数量。
关键条件：
- 鸡是时间点，牛是时间区间。
- 时间从小到大处理时，已经开始但还没过期的牛都可能匹配当前鸡。
- 为了给未来留下更多选择，当前鸡应该匹配结束时间最早的可用牛。
思路分析
按时间扫描鸡：
- 将鸡时间排序。
- 将牛按开始时间
A排序。 - 对每只鸡，把所有
A <= T的牛加入最小堆，堆键是结束时间B。 - 弹出所有
B < T的过期牛。 - 若堆非空，匹配
B最小的牛。
这个贪心安全：结束越早的牛越紧急，当前不匹配它，未来更可能错过。
CPP 完整代码
✅ 完整代码：Why Did the Cow Cross the Road
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// USACO 官方文件 I/O 可按需打开：
// freopen("helpcross.in", "r", stdin);
// freopen("helpcross.out", "w", stdout);
int c, n;
cin >> c >> n;
vector<int> chicken(c);
for (int &t : chicken) cin >> t;
vector<pair<int, int>> cows(n); // {开始时间, 结束时间}
for (auto &[a, b] : cows) cin >> a >> b;
sort(chicken.begin(), chicken.end());
sort(cows.begin(), cows.end());
priority_queue<int, vector<int>, greater<int>> availableEnd;
int cowIndex = 0;
int matched = 0;
for (int t : chicken) {
while (cowIndex < n && cows[cowIndex].first <= t) {
availableEnd.push(cows[cowIndex].second);
cowIndex++;
}
while (!availableEnd.empty() && availableEnd.top() < t) {
availableEnd.pop(); // 已经过期，不能再匹配
}
if (!availableEnd.empty()) {
availableEnd.pop(); // 当前鸡匹配结束最早的牛
matched++;
}
}
cout << matched << "\n";
return 0;
}
复杂度： 排序 O((C+N) log(C+N))，每头牛最多进出堆一次，总复杂度 O((C+N) log N)。
易错点提醒
- 按结束时间排序后直接双指针。 鸡时间点和牛区间交错，仅靠两个指针不够，需要堆维护当前可选牛。
- 忘记删除过期牛。
B < T的牛无法被当前或未来鸡匹配，必须弹出。 - 匹配结束最晚的牛。 应匹配结束最早者，把更宽松的牛留给未来。
- 边界条件写错。 若
A <= T <= B，则B == T仍然可匹配，不应弹出。
拓展思考
这类题属于「按时间扫描 + 最紧急优先」模型。若每只鸡有多个时间段、每头牛也需要多个资源，问题可能升级为区间调度或二分图匹配。
⚠️ 常见错误
- 双指针前忘排序： 配对求和的双指针技术只在有序数组上有效。不排序会遗漏一些对或得到错误答案。
- 找到对时只移动一个指针： 找到匹配的对时，必须同时移动
left++和right--。只移动一个会遗漏一些对（除非不需要考虑重复）。 - 窗口大小差一： 窗口
[left, right]的大小是right - left + 1，不是right - left。 - 忘记处理空答案： 对「最小子数组」问题，将
minLen初始化为INT_MAX，输出前检查它是否改变了。
本章总结
📌 核心要点
| 技术 | 前提条件 | 时间 | 空间 | 核心思想 |
|---|---|---|---|---|
| 双指针（配对） | 有序数组 | O(N) | O(1) | 从两端逼近，消除不可能的对 |
| 双指针（三数之和） | 有序数组 | O(N²) | O(1) | 固定一个，对其余用双指针 |
| 滑动窗口（固定） | 任意 | O(N) | O(1) | 加新元素，减旧元素 |
| 滑动窗口（可变） | 任意 | O(N) | O(1~N) | 右端扩张，左端收缩 |
❓ 常见问题
Q1：双指针一定需要排序吗？
A：不一定。「反向双指针」（如配对求和）需要排序；「同向双指针」（如滑动窗口）不需要。关键是单调性——指针只朝一个方向移动。
Q2：滑动窗口和前缀和都能计算区间和——该用哪个？
A：固定大小窗口的和/最大值，滑动窗口更直观。任意区间查询，前缀和更通用。滑动窗口只能处理「连续移动的窗口」；前缀和可以回答任意 [L,R] 查询。
Q3：滑动窗口能同时处理「满足条件的最长子数组」和「满足条件的最短子数组」吗？
A：两者都可以，但逻辑略有不同。「最长」：右端扩张直到条件不满足，再从左收缩直到条件重新满足。「最短」：右端扩张直到条件满足，再从左收缩直到条件不再满足，全程记录最小长度。
Q4：双指针如何处理重复元素？
A：取决于题目。若需要「所有不同对的值」，找到对后做
left++; right--并跳过重复值。若需要「所有对的数量」，需要仔细统计重复项（可能需要额外的计数逻辑）。
🔗 与后续章节的联系
- 第 3.2 章（前缀和）：前缀和与滑动窗口互补——前缀和适合离线查询，滑动窗口适合在线处理
- 第 3.3 章（排序）：排序是双指针的前提——反向双指针需要有序数组
- 第 3.5 章（单调性）：单调双端队列可以增强滑动窗口——在
O(N)时间内维护窗口最小/最大值 - 第 6.1–6.3 章（DP）：一些问题（如 LIS 变体）可以用双指针优化
练习题
题目 3.4.1 — 配对计数 🟢 简单
给定 N 个整数和目标值 T，统计满足 arr[i] + arr[j] = T 的对 (i < j) 的数量。
提示
先排序数组，从两端用双指针。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, T; cin >> n >> T;
vector<int> a(n); for (int& x : a) cin >> x;
sort(a.begin(), a.end());
long long cnt = 0;
int L = 0, R = n - 1;
while (L < R) {
int s = a[L] + a[R];
if (s == T) {
if (a[L] == a[R]) {
// [L..R] 内所有对都有效
long long len = R - L + 1;
cnt += len * (len - 1) / 2;
break;
}
// 统计两侧的重复值
long long cl = 1, cr = 1;
while (L+1 < R && a[L+1] == a[L]) { cl++; L++; }
while (R-1 > L && a[R-1] == a[R]) { cr++; R--; }
cnt += cl * cr;
L++; R--;
} else if (s < T) L++;
else R--;
}
cout << cnt << "\n";
}
复杂度： O(N log N)。
题目 3.4.2 — 最大平均子数组 🟡 中等 找恰好长度为 K 的连续子数组，使其平均值最大。
提示
固定大小滑动窗口：维护运行和，每步加 A[i] 减 A[i-K]。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k; cin >> n >> k;
vector<double> a(n); for (double& x : a) cin >> x;
double windowSum = 0;
for (int i = 0; i < k; i++) windowSum += a[i];
double maxSum = windowSum;
for (int i = k; i < n; i++) {
windowSum += a[i] - a[i-k];
maxSum = max(maxSum, windowSum);
}
cout << fixed << setprecision(5) << maxSum / k << "\n";
}
复杂度： O(N)。
题目 3.4.3 — 最小覆盖子串 🔴 困难 给定字符串 S 和字符串 T，找 S 中包含 T 所有字符的最短子串。
提示
可变滑动窗口，用频率映射记录所需字符，满足所有 T 中字符时从左收缩。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
string S, T; cin >> S >> T;
unordered_map<char,int> need, have;
for (char c : T) need[c]++;
int formed = 0, required = need.size();
int L = 0, minLen = INT_MAX, minL = 0;
for (int R = 0; R < (int)S.size(); R++) {
have[S[R]]++;
if (need.count(S[R]) && have[S[R]] == need[S[R]]) formed++;
while (formed == required) {
if (R - L + 1 < minLen) { minLen = R-L+1; minL = L; }
have[S[L]]--;
if (need.count(S[L]) && have[S[L]] < need[S[L]]) formed--;
L++;
}
}
if (minLen == INT_MAX) cout << "no solution\n";
else cout << S.substr(minL, minLen) << "\n";
}
样例： S="ADOBECODEBANC"，T="ABC" → "BANC" 复杂度： O(|S| + |T|)。
🏆 挑战题：USACO 2017 February Bronze——为何奶牛过马路 给定网格中的奶牛和它们的目的地，找哪头奶牛最快到达目的地。对排序好的区间用双指针/贪心方法。