双指针与尺取法

前言

上一章学了二分搜索——在排序数组里找东西，$O(\log n)$。但有些问题的答案不是”某个位置”，而是”一对位置”或者”一段区间”。比如”在排序数组中找两个数使它们的和等于 $K$“——二分可以做，但需要先固定一个数再二分另一个，$O(n \log n)$。有没有 $O(n)$ 的做法？

有。让两个指针从数组两端出发，根据和的大小决定移动哪个指针——每次只移动一个，最多移动 $n$ 步，总计 $O(n)$。这就是对撞指针。

另一种场景：“找最短的连续区间使和 $\ge S$“。两个指针从同一端出发，右指针扩展窗口，左指针在条件满足时收缩——每个元素最多进出窗口各一次，也是 $O(n)$。这就是尺取法（滑动窗口）。

双指针的核心思想：两个指针单调移动，总共 $O(n)$ 步。把暴力 $O(n^2)$ 变成 $O(n)$。

问题的本质

对撞指针：从两端向中间

适用于排序数组中”找一对满足条件的数”。左指针 l 从 0 开始，右指针 r 从 $n-1$ 开始。根据 a[l] + a[r] 和目标的关系决定移动哪个指针。

为什么一定正确？因为数组有序：l 右移让 $a[l]$ 变大（从而和变大），r 左移让 $a[r]$ 变小（从而和变小）。每次移动都更接近目标，不会漏掉答案。

尺取法：滑动窗口

适用于”找满足某条件的连续区间”。右指针不断扩展窗口，左指针在条件满足时收缩。因为两个指针都只往一个方向走，总共 $O(n)$。

理论 + 代码

对撞指针

// 在排序数组中找两个数使和等于 K
int l = 0, r = n - 1;
while (l < r) {
    int sum = a[l] + a[r];
    if (sum == K) {
        // 找到了
        break;
    } else if (sum < K) {
        l++;    // ① 和太小，左指针右移
    } else {
        r--;    // ② 和太大，右指针左移
    }
}

• ① l++：让 a[l] 变大，从而使和变大。能不能 r++？不行，r 已经在最右边了。
• ② r--：让 a[r] 变小，从而使和变小。能不能 l--？不行，l 已经在最左边了。

走一遍过程：数组 [1, 3, 5, 7, 9]，$K = 10$。

步骤	l	r	a[l]	a[r]	和	判断	操作
1	0	4	1	9	10	== K	找到！

一步搞定。换 $K = 8$：

步骤	l	r	a[l]	a[r]	和	判断	操作
1	0	4	1	9	10	> 8	r=3
2	0	3	1	7	8	== 8	找到！

尺取法（滑动窗口）

// 找最短的连续子数组使和 >= S
int l = 0, sum = 0, ans = n + 1;
for (int r = 0; r < n; r++) {
    sum += a[r];                 // ① 右指针扩展，纳入 a[r]
    while (sum >= S) {           // ② 窗口满足条件
        ans = min(ans, r - l + 1);  // ③ 记录答案
        sum -= a[l];             // ④ 尝试收缩左指针
        l++;
    }
}

• ① r 每次走一步，把新元素纳入窗口。
• ②③ 如果窗口满足条件，记录答案。
• ④ l 右移，缩小窗口看能不能更短。

走一遍过程：数组 [2, 3, 1, 2, 4, 3]，$S = 7$。

r	a[r]	sum	满足?	操作	ans
0	2	2	否	—	∞
1	3	5	否	—	∞
2	1	6	否	—	∞
3	2	8	是	l→0, sum=6, l=1	4
4	4	10	是	l→1, sum=7, l=2; l→2, sum=6, l=3	3
5	3	9	是	l→3, sum=7, l=4; l→4, sum=3, l=5	2

最终 ans=2。最短子数组是 [4, 3]，长度 2，和为 7。✓

例题

例题 1：M&A 020 — Choose Cards 2（★2）

题目：$N$ 张卡片，第 $i$ 张写着整数 $A_i$。从中选 5 张，使 5 张的数字之和恰好为 1000 的选法有多少种？

数据范围：$5 \le N \le 100$，$1 \le A_i \le 1000$

—— AtCoder M&A 020

思路：5 层循环 $O(N^5) = 10^{10}$，太慢。但我们可以用折半枚举（meet-in-the-middle）：把 5 张分成两组——前 2 张和后 3 张。

枚举所有 2 张的组合（$C(N,2) \le 4950$），存入数组 $L$；枚举所有 3 张的组合（$C(N,3) \le 161700$），存入数组 $R$。对每个 $L[i]$，在 $R$ 中查找 $1000 - L[i]$。对 $R$ 排序后可以用二分或双指针。

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int A[110];
    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);

    // ① 枚举选 2 张的所有组合和
    vector<int> L;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            L.push_back(A[i] + A[j]);

    // ② 枚举选 3 张的所有组合和
    vector<int> R;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            for (int k = j + 1; k < N; k++)
                R.push_back(A[i] + A[j] + A[k]);

    sort(R.begin(), R.end());    // ③ 排序 R

    long long ans = 0;
    for (int i = 0; i < (int)L.size(); i++) {
        int target = 1000 - L[i];
        // ④ 在 R 中统计 target 出现的次数
        auto lo = lower_bound(R.begin(), R.end(), target);
        auto hi = upper_bound(R.begin(), R.end(), target);
        ans += hi - lo;
    }
    printf("%lld\n", ans);
}

逐行解析：

• ①② $L$ 存 2 张的和，$R$ 存 3 张的和。大小分别是 $C(N,2)$ 和 $C(N,3)$，最大约 $4950$ 和 $161700$。
• ③ 排序 $R$，为二分查找做准备。
• ④ lower_bound 和 upper_bound 夹出 target 在 $R$ 中出现的次数。

---

例题 2：Tessoku Book — A14 Four Boxes

题目：有 4 个箱子 A、B、C、D，各有 $N$ 张写有整数的卡片。从每个箱子各选 1 张，是否存在选法使 4 张卡片的数字之和恰好等于 $K$？

数据范围：$1 \le N \le 1000$，$1 \le K \le 10^8$

—— AtCoder Tessoku Book A14

思路：4 层循环 $O(N^4) = 10^{12}$，太慢。折半枚举：把 A+B 的和存入数组 $L$，C+D 的和存入数组 $R$，然后对每个 $L[i]$ 检查 $K - L[i]$ 是否在 $R$ 中。

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int N;
    long long K;
    scanf("%d%lld", &N, &K);
    vector<long long> A(N), B(N), C(N), D(N);
    for (int i = 0; i < N; i++) scanf("%lld", &A[i]);
    for (int i = 0; i < N; i++) scanf("%lld", &B[i]);
    for (int i = 0; i < N; i++) scanf("%lld", &C[i]);
    for (int i = 0; i < N; i++) scanf("%lld", &D[i]);

    // ① A + B 的所有组合和
    vector<long long> AB;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            AB.push_back(A[i] + B[j]);

    // ② C + D 的所有组合和
    vector<long long> CD;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            CD.push_back(C[i] + D[j]);

    sort(CD.begin(), CD.end());    // ③ 排序

    bool found = false;
    for (int i = 0; i < (int)AB.size(); i++) {
        long long target = K - AB[i];
        // ④ 二分查找
        if (binary_search(CD.begin(), CD.end(), target)) {
            found = true;
            break;
        }
    }
    printf("%s\n", found ? "Yes" : "No");
}

逐行解析：

• ①② 各 $N^2 = 10^6$ 种组合。比 $N^4$ 小了一百万倍。
• ③④ 排序后用 binary_search 检查是否存在。总时间 $O(N^2 \log N)$。

---

例题 3：Tessoku Book — A13 Close Pairs（双指针解法）

题目：$N$ 个严格递增的整数 $A_1 < A_2 < \cdots < A_N$。选两个不同的数，差不超过 $K$（$A_j - A_i \le K$）的选法有多少种？

数据范围：$1 \le N \le 100000$，$1 \le K \le 10^9$

—— AtCoder Tessoku Book A13

思路：这道题在 00-02 排序 中用 upper_bound 解过。现在用双指针的思路再做一遍——更高效。

维护右指针 r。对每个 i，让 r 尽量右移直到 $A[r] - A[i] > K$。那么满足条件的 $j$ 有 $r - i - 1$ 个。关键是 r 只往右不往左——因为 $i$ 增大后，$A[r] - A[i]$ 只会变小。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    long long K;
    scanf("%d%lld", &N, &K);
    long long A[100010];
    for (int i = 0; i < N; i++)
        scanf("%lld", &A[i]);

    long long ans = 0;
    int r = 0;
    for (int i = 0; i < N; i++) {
        while (r < N && A[r] - A[i] <= K)    // ① r 尽量右移
            r++;
        // 现在 A[r] - A[i] > K（或 r == N）
        ans += r - i - 1;    // ② 满足条件的 j 有 r-i-1 个
    }
    printf("%lld\n", ans);
}

逐行解析：

• ① r 从不回退。因为 $i$ 增大后 $A[i]$ 变大，之前 $A[r] - A[i] \le K$ 的 $r$ 仍然满足 $A[r] - A[i'] \le K$（$i' > i$ 时 $A[r] - A[i'] < A[r] - A[i]$）。
• ② r 是第一个不满足条件的位置，所以满足条件的是 $i+1, i+2, \ldots, r-1$，共 $r - i - 1$ 个。

复杂度：两个指针各走 $N$ 步，$O(N)$。

---

例题 4：M&A 019 — Choose Cards 1（★1）

题目：$N$ 张卡片，每张涂有颜色 1（红）、2（黄）或 3（蓝）。选 2 张同色卡片的选法有多少种？

数据范围：$2 \le N \le 500000$，$1 \le A_i \le 3$

—— AtCoder M&A 019

思路：统计每种颜色各有多少张。如果红色有 $c$ 张，选 2 张红色的选法就是 $C(c, 2) = c(c-1)/2$。三种颜色求和。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    long long cnt[4] = {};    // ① 颜色计数器
    for (int i = 0; i < N; i++) {
        int a;
        scanf("%d", &a);
        cnt[a]++;    // ② 统计每种颜色出现次数
    }

    long long ans = 0;
    for (int c = 1; c <= 3; c++)
        ans += cnt[c] * (cnt[c] - 1) / 2;    // ③ C(cnt[c], 2)

    printf("%lld\n", ans);
}

逐行解析：

• ② 桶计数：$cnt[c]$ = 颜色 $c$ 的卡片数。
• ③ 组合公式 $C(n,2) = n(n-1)/2$。

---

例题 5：M&A 067 — Cross Sum（★2）

题目：（M&A 067 = T90 004）给定 $H \times W$ 的矩阵，求每个元素 $A_{i,j}$ 的”十字和”——第 $i$ 行所有元素之和加上第 $j$ 列所有元素之和，再减去 $A_{i,j}$（因为被加了两次）。输出整个矩阵的十字和。

数据范围：$1 \le H, W \le 2000$，$1 \le A_{i,j} \le 99$

—— AtCoder M&A 067

思路：预处理每行的和 $R[i]$ 和每列的和 $C[j]$。对每个 $(i,j)$，十字和 = $R[i] + C[j] - A_{i,j}$。

代码：

#include <cstdio>
using namespace std;

int A[2010][2010];
long long R[2010], C[2010];

int main() {
    int H, W;
    scanf("%d%d", &H, &W);
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            scanf("%d", &A[i][j]);

    // ① 行和
    for (int i = 0; i < H; i++) {
        R[i] = 0;
        for (int j = 0; j < W; j++)
            R[i] += A[i][j];
    }
    // ② 列和
    for (int j = 0; j < W; j++) {
        C[j] = 0;
        for (int i = 0; i < H; i++)
            C[j] += A[i][j];
    }

    // ③ 输出十字和
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (j) printf(" ");
            printf("%lld", R[i] + C[j] - A[i][j]);
        }
        printf("\n");
    }
}

逐行解析：

• ①② 分别预处理行和、列和，各 $O(HW)$。
• ③ $R[i] + C[j] - A[i][j]$：行和 + 列和 - 自己（被算了两次）。这个”多算一次要减去”的思想和容斥原理如出一辙。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 3 章

• 3.3 B13 Supermarket 2（しゃくとり法/尺取法 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 020 Choose Cards 2（折半枚举 N≤100）【例题】
• 019 Choose Cards 1（同色对计数）【例题】
• 022 Choose Cards 3（双指针/哈希 N≤2×10⁵）

系统练习 — 競技プログラミングの鉄則

• A14 Four Boxes（折半枚举）【例题】
• A13 Close Pairs（排序+双指针）【例题】
• B14 Another Subset Sum（二分搜索+双指针）

实战练习 — 競プロ典型 90 問

• 067 Cross Sum（★2，行列预计算）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化