第 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);
}
}
⚠️ 常见错误
- 双指针前忘排序： 配对求和的双指针技术只在有序数组上有效。不排序会遗漏一些对或得到错误答案。
- 找到对时只移动一个指针： 找到匹配的对时，必须同时移动
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——为何奶牛过马路 给定网格中的奶牛和它们的目的地，找哪头奶牛最快到达目的地。对排序好的区间用双指针/贪心方法。