双指针

1 从重复枚举到双指针

枚举两个位置时，最直接的写法往往是两层循环：固定第一个位置，再让第二个位置从头找一遍。问题是：第一个位置移动以后，第二个位置真的需要重新找吗？

如果能证明一部分候选已经不可能成为答案，或者已经处理完毕，就可以把进度保留下来，用两个下标继续向前处理。这两个下标通常叫做“指针”，不要求使用 C++ 的指针类型。

本章先看从两端向中间移动的相向双指针，再看都向右移动的同向双指针。重点是移动依据，以及为什么移动后不会漏掉答案。

2 相向双指针：两数之和

2.1 题目与样例

给定 $n$ 个整数和目标和 $m$，在两个不同位置选数，使它们的和等于 $m$。保证有解；若有多对，输出其中较小值最小的一对，按从小到大输出。$2\le n\le 10^5$，元素和目标和均在 int 范围内。

输入第一行为 $n$，第二行为数组，第三行为 $m$。

1
2
3

9
21 4 5 6 13 65 32 9 23
37

输出：

1

5 32

2.2 从枚举到排除

直接做法要枚举多少对？

枚举所有 $i<j$，检查 $a_i+a_j=m$，并保留较小值最小的一对，共有 $n(n-1)/2$ 对，时间为 $O(n^2)$。

怎样让一次比较排除不止一对？

先从小到大排序，得到

排序后，固定一个数时，它与其他数的和也随搭档增大而不减。本题只输出数值，不依赖原来的位置关系，所以可以排序；若要求原下标，应连同原下标一起排序。

先让 $l=1,r=n$。当前只考虑区间 $[l,r]$ 内两个不同位置的配对，比较最小值 $a_l$ 与最大值 $a_r$ 的和。

如果最小值加最大值还小于 $m$，能排除谁？

对任意 $l<k\le r$，都有

也就是说，$a_l$ 即使选当前最大的搭档也不够，换任何搭档都不可能成功。于是可以排除以当前位置 $l$ 为较小端的所有配对，令 l++。

如果最小值加最大值已经大于 $m$，又能排除谁？

对任意 $l\le k<r$，都有

也就是说，$a_r$ 即使选当前最小的搭档也太大，换任何搭档都不可能成功。于是可以排除所有使用当前位置 $r$ 的配对，令 r--。

注意，大于目标时排除的是右端，小于目标时排除的是左端。移动的理由是这个端点没有任何可行搭档。

如果恰好相等，为什么可以直接输出？

此前被左指针越过的每个位置都已经证明不可能有解；而当前区间里 $a_l$ 最小。因此找到的第一对满足“较小值最小”的要求。右端只会移除不可能参与答案的位置，不会误删搭档。

这也说明：每次移动后，若答案尚未找到，它一定仍在当前区间内。不断缩小区间，就不会漏掉答案。

2.3 走一遍样例

排序后为 $[4,5,6,9,13,21,23,32,65]$。

2.4 代码与复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    long long m;
    cin >> m;
    sort(a.begin() + 1, a.end());

    int l = 1, r = n;
    while (l < r) {
        long long sum = 1LL * a[l] + a[r];
        if (sum == m) {
            cout << a[l] << ' ' << a[r] << '\n';
            return 0;
        }
        if (sum < m) ++l;  // a[l] 与最大的搭档相加仍不足
        else --r;         // a[r] 与最小的搭档相加已超出
    }
    // 本题保证有解；若取消保证，可以在这里输出无解标记。
    return 0;
}

循环条件是 l < r，因为不能把同一个位置使用两次。数值可以相同，例如 [5,5] 能组成 $10$，关键是位置不同。求和用 long long，避免两个 int 相加溢出。

排序为 $O(n\log n)$，之后每次至少移动一个指针，扫描为 $O(n)$，所以总时间是 $O(n\log n)$。若输入本来有序，便只需 $O(n)$。存储数组为 $O(n)$，扫描只需 $O(1)$ 额外空间。

也可以排序后枚举一个位置，用二分查找补数 $m-a_i$，总时间同样是 $O(n\log n)$；双指针进一步利用了相邻候选之间的大小关系，使扫描时不必为每个位置重新查找。

3 相向双指针：判断回文串

回文串要求从左往右、从右往左读都一样。例如 abcba 是回文串，abcca 不是。

怎样直接检查？

复制一份字符串并反转，再与原串比较，可以得到答案。但按定义逐对比较首尾字符，就不需要那份副本。

一对字符相等以后，为什么可以同时向内移动？

这两个位置的镜像搭档已经确定，不会再与其他位置配对。比较完就完成了它们的检查，剩下只需判断中间的子串。

若发现一对不同，立即返回 false；若所有成对位置都相同，就是回文串。奇数长度的中心字符与自身对应，不需要再比较。

3.1 代码与边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 双指针判断回文:两根指针从两端向中间夹,一步比一对
bool is_palindrome(const string &s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false; // 第一个不等就是答案
        i++;
        j--;
    }
    return true;
}

// 数组版:长度放在参数里,判 a[1..n]
bool is_palindrome(int a[], int n) {
    int i = 1, j = n;
    while (i < j) {
        if (a[i] != a[j]) return false;
        i++;
        j--;
    }
    return true;
}

字符串版使用从 $0$ 开始的下标，数组版使用从 $1$ 开始的下标。两者都用 i < j，保证左右位置不同。

字符串版先将 size() 转为 int 再减 $1$，空串时右端为 $-1$，循环不执行；单字符同样直接返回 true。是否忽略大小写或标点，应由题意决定。

时间为 $O(n)$，额外空间为 $O(1)$。这里不需要排序，也不依赖字符大小的单调性；移动的依据是镜像位置已经检查完毕。排序会改变字符串，不能用来帮助判定原串是否回文。

4 同向双指针：最短达标子数组

4.1 题目与样例

给定 $n$ 个正整数和正整数 $S$，求区间和至少为 $S$ 的最短非空连续子数组的长度；不存在则输出 $0$。$1\le n\le 10^5$，$1\le a_i,S\le 10^9$。

输入第一行为 $n,S$，第二行为数组。

1
2

6 7
2 3 1 2 4 3

输出：

1

2

最后两个数 $4+3=7$，长度为 $2$；没有单个元素达到 $7$。

4.2 为什么左右端点可以一直向右

直接枚举区间，重复在哪里？

枚举左端，再从该位置开始向右累加，直到区间和达标。每换一个左端，右端又要从头走；即使及时停止，最坏仍需 $O(n^2)$。

当前区间和不足时，应该怎样找新候选？

维护窗口 $[l,r]$ 和它的元素和 sum。因为所有数为正，删除左端只会使和更小，不能让一个不达标的窗口达标。此时应右移 $r$，加入新元素。

窗口达标后，怎样寻找更短的答案？

先用长度 $r-l+1$ 更新答案，再尝试删去左端，即 sum -= a[l]、l++。如果仍然达标，就继续记录、继续缩短；直到窗口不再达标，再向右扩展。

不能只用一次 if 就结束收缩：同一个右端可能对应多个达标窗口。例如右端到达样例的 $4$（下标 $5$）后，$[2,5]$ 和 $[3,5]$ 都达标，应继续尝试更短的窗口。

被删掉的左端，以后为什么不需要回来？

一个左端 $l$ 被删掉时，我们已经在它第一次达标的右端 $r$ 处记录了长度。由于元素为正，更早的右端不达标；以后右端更大，以这个 $l$ 开头的区间只会更长，不可能改进答案。因此这个左端的任务已经完成，可以永久舍弃。

对于当前尚未达标的左端，右端继续向右；对于已经达标的左端，记录后让左端向右。每个左端只需找到第一个达标的右端，找到后就不必再回头。

4.3 窗口怎样变化

下面摘出样例中几次达标后的收缩。下标从 $1$ 开始。

4.4 代码与复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    cin >> n >> S;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int l = 1, ans = n + 1;
    long long sum = 0;
    for (int r = 1; r <= n; ++r) {
        sum += a[r];
        while (l <= r && sum >= S) {
            ans = min(ans, r - l + 1);
            sum -= a[l];
            ++l;
        }
    }
    cout << (ans == n + 1 ? 0 : ans) << '\n';
    return 0;
}

开始时令 $l=1$、sum = 0，表示尚未加入元素。每次先加入右端，再用 while 记录并收缩达标窗口。注意顺序：先记录当前长度，再删除左端。

如果某个元素自己就达到 $S$，最终会记录长度 $1$，之后窗口可以暂时为空。sum 的最大值可达 $10^{14}$，应使用 long long。

右端只前进 $n$ 次；左端在整个 while 的所有执行中合计也只前进至多 $n$ 次。因此时间为 $O(n)$，存储数组为 $O(n)$，额外维护状态为 $O(1)$。

4.5 为什么不能直接处理负数

上面的推理依赖“扩展使和增大、收缩使和减小”。例如数组 $[1,-1,5]$，$S=5$：

• 扩展到最后时，窗口 $[1,3]$ 的和为 $5$，先记录长度 $3$。
• 删去左端的 $1$ 后，$[-1,5]$ 的和为 $4$，按上面的代码会停止收缩。
• 但再删去 $-1$，窗口 $[5]$ 的和反而变为 $5$，长度 $1$ 才是答案。

有负数时，“当前不达标，所以继续收缩也不会达标”不再成立，不能直接套用这个窗口。反过来，两数之和允许负数：它依赖的是排序后的大小关系，并不要求每个数为正。

同向双指针不止能处理区间和，也可以维护字符计数等信息。能否使用滑动窗口，仍需针对具体条件证明左右端点的移动不会漏解。

5 总结：指针为什么不用回头

三个例子都只保留两个位置，但保证正确的理由各不相同。两数之和需要有序；回文依赖镜像配对；本章的窗口依赖元素为正。不能只看代码都有 l++、r--，就互相套用。

有嵌套循环，为什么还可能是线性的？

以滑动窗口为例，外层每次让右端前进一格；内层可能连续移动左端，但下一轮从上次的位置继续。两个指针在整个算法中各前进至多 $n$ 次，合计仍为 $O(n)$。这里统计的是全部循环执行完后的总移动次数。

实际做题时，先说清指针所代表的范围和维护的信息，再证明每次移动不会漏解，最后数总移动次数。若某个指针仍要反复退回起点，就不能直接声称是 $O(n)$。

6 练习

• 将两数之和改为“可能无解”，返回有解与否；再测试 [5,5]、目标和为 $10$ 的情况。
• 写出两数之和每次舍弃端点时的不等式，解释为什么负数不会破坏有序数组上的排除结论。
• 给最短达标子数组增加“输出区间端点”的要求，并约定多个最短区间时如何选择。
• 对照 [1,-1,5]、$S=5$，找出普通滑动窗口漏解的具体一步。

7 进阶例题：回文中的双指针

下面通过压缩字符串与补字符两个例题，继续讨论指针能否按段移动，以及双指针之外还需要什么工具。

7.1 例题：luogu P17828: [CSP-J 2026] 回文串 / string（民间数据）

7.1.1 题意

长度为 $L$ 的字符串 $S$ 不直接给出，而是压缩成 $n$ 段：第 $i$ 段是 $a_i$ 个字符 $c_i$，依次拼接就是 $S$。相邻两段可以同色。每次可以把任意一个位置的字符改成任意小写字母，问最少改几个位置能让 $S$ 变成回文串。

• $1 \le n \le 2\times 10^5$，$1 \le a_i \le 10^9$
• 于是 $L = \sum a_i$ 最大到 $2\times 10^{14}$，串本身是造不出来的

7.1.2 第一步：把"最少修改"翻译成"数出多少对不等"

对每个 $i < L+1-i$，把 $(s_i, s_{L+1-i})$ 叫做一对镜像位置。

证明（下界）：若某一对镜像位置字符不同，最终它们必须相同，而一次修改只动一个位置，所以这一对至少贡献一次修改。

证明（上界）：对每一对不相等的镜像位置，只改左边（或只改右边）那一个字符，把它改成另一边即可。不同镜像位置集合互不相交（一个位置只属于一对），所以这样一共正好改"对数"次。

两条夹起来，答案就是不相等的对数。长度是奇数时，最中间那个位置没有镜像搭档，它爱是什么是什么，不产生任何代价。

7.1.3 第二步：不能展开，就让指针走"段"

既然答案只跟"某一对镜像位置的字符是否相同"有关，我们仍然用双指针的思想：左指针在最左端、右指针在最右端，一对一对往中间收。

区别只在于：指针走的不是字符，而是段。段 $i$ 还剩 remL 个字符没被配对，段 $j$ 还剩 remR 个，那么这一轮能一次配掉

对。这 $k$ 对的左半边全是 c[i]、右半边全是 c[j]：

• c[i] == c[j]：这 $k$ 对全部相等，一次贡献 $0$；
• c[i] != c[j]：这 $k$ 对全部不等，一次贡献 $k$。

配完就把两边的剩余量各减 $k$，谁先减到 $0$ 谁的段指针就往里挪一格，并把新段的全长装进剩余量。

7.1.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// P17828 [CSP-J 2026] 回文串 / string
// 串用游程压缩给出,不能展开;左右指针在"段"上相向走
#include <bits/stdc++.h>
using namespace std;

int n;
long long a[200005];  // a[i]: 第 i 段有多少个字符
char c[200005];       // c[i]: 第 i 段的字符

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> c[i];

    long long ans = 0;
    int li = 1, ri = n;              // 还没配完的最外层两段
    long long remL = a[li];          // 左段还剩几个字符没配
    long long remR = a[ri];          // 右段还剩几个字符没配

    while (li < ri) {
        long long k = min(remL, remR);   // 这次能配 k 对
        if (c[li] != c[ri]) ans += k;    // 每对不等都要改一个位置
        remL -= k;
        remR -= k;
        if (remL == 0) {
            li++;
            remL = a[li];            // li 不会超过 ri,读完正好退出循环
        }
        if (remR == 0) {
            ri--;
            remR = a[ri];
        }
    }
    // li == ri 时,中间剩的那段是自己和自己配,字符必然相同,贡献 0

    cout << ans << "\n";
    return 0;
}

样例 1（aabbc）走一遍：段是 a2 b2 c1。左边 2 个 a 对右边 1 个 c，$k=1$ 且 a != c，答案加 1，左段还剩 1 个 a；接着 1 个 a 对 1 个 b，$k=1$ 且不等，答案加 1；共 2，与样例一致。

7.1.5 复杂度

• 时间：$O(n)$。每一轮至少有一个段指针前进一格，而指针只走 $n$ 格。
• 空间：$O(n)$，只存段。
• 注意 $L$ 只能当数值用（算剩余量、累加答案），绝不能当数组下标。答案最大约 $10^{14}$，int 装不下，ans 要 long long。

7.1.6 容易踩的坑

• 段指针挪到 li == ri 时就该停：中间剩下的那段是自己和自己配对，字符必然相同，贡献恒为 0。
• 相邻同色的段（比如 a a a）不用合并，代码照样对；只是合并之后循环轮数更少。别为了合并把 $a_i$ 累加到 int 溢出。
• 只有一段时（$n=1$）答案直接是 0，循环一次都不进。

7.2 例题：luogu P10905: [蓝桥杯 2024 省 C] 回文字符串

7.2.1 题意

给定只含小写字母的串 $S$，可以在 $S$ 的开头加入任意多个只由 l、q、b 组成的字符，问能否把 $S$ 变成回文串。多组数据，$1 \le T \le 10$，$1 \le \sum |S| \le 10^6$。

7.2.2 把"补字符"翻译成两条约束

设补上的串为 $P$，长度 $m$，目标是 $P+S$ 是回文串。先说明 $m$ 只需要考虑 $0 \le m \le n$：当 $m > n$ 时，$S$ 的每个字符的对称位置都落在 $P$ 里，条件退化成"$S$ 全是 l/q/b"，而这种情况取 $m = n$ 也能做到。所以下面只讨论 $m \le n$。

看 $P+S$ 里位置 $t$（从 0 数）的对称位置 $m+n-1-t$：

• $t \ge m$：两边都落在 $S$ 里，这一层要求 $S[t-m] = S[n-1-t]$。把所有这样的 $t$ 写开，就是一句话——$S$ 的长度为 $n-m$ 的前缀必须是回文串（这部分只能用双指针去验，补字符帮不上忙）。
• $t < m$：左边是补的字符，右边落在 $S$ 里，要求 $P[t] = S[n-1-t]$。而 $P[t]$ 可以随便取，只要属于 {l,q,b}，所以这一层唯一的限制是——$S$ 的长度为 $m$ 的后缀必须全是 l、q、b。

把 $x = n-m$ 代进去，结论是：

7.2.3 一个 $O(n^2)$ 的部分分写法

直接枚举 $x$，前缀回文用双指针验，后缀字符集用一次扫描验：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// P10905 [蓝桥杯 2024 省 C] 回文字符串
// 朴素做法:枚举前面补了几个字符 O(n^2),能过 |S| <= 1000 的 50 分
#include <bits/stdc++.h>
using namespace std;

string s;

// s 的长度为 x 的前缀是不是回文
bool pre_palindrome(int x) {
    int i = 0, j = x - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}

// 补上的字符只能取 l q b
bool can_fill(char ch) {
    return ch == 'l' || ch == 'q' || ch == 'b';
}

bool solve() {
    int n = (int)s.size();
    // 枚举 x:前 x 个字符自己回文,后 n-x 个字符交给补的 l/q/b
    for (int x = n; x >= 0; x--) {
        bool ok = true;
        for (int i = x; i < n; i++)
            if (!can_fill(s[i])) ok = false;
        if (ok && pre_palindrome(x)) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        cout << (solve() ? "Yes" : "No") << "\n";
    }
    return 0;
}

这个写法在 $|S| \le 1000$ 的 50% 数据上够用。想过满分得把"$S$ 有哪些回文前缀"一次算出来，那已经不是双指针的事了：正反字符串哈希比对、KMP（用 S + '#' + reverse(S) 找 border）、Manacher，都属于字符串算法那条线。

7.3 延伸题目：区分双指针承担的工作

• luogu P10902: [蓝桥杯 2024 省 C] 回文数组（普及−）：同样是"配对"，但一次操作能同时动相邻两个数，代价可以在相邻对之间共享/传递。样例 1 2 3 4 答案是 3，而不是把两对的差分别相加得到的 4，就说明了这点。外层仍用双指针配对，代价怎么算要自己推。
• luogu P16960: [SCCPC 2026] 那一天的回文字符串（普及−）：奇/偶下标上的字符可以各自重排，问能否变回文。本质是"配对能不能凑齐"的计数/匹配，双指针只是外层框架。
• luogu P1015: [NOIP 1999 普及组] 回文数（普及−）：主题是模拟 + 高精度，但判定回文这一步正好用本模板（位数不多，双指针 $O(\text{位数})$）。
• luogu P1206: [USACO1.2] 回文平方数、luogu P2010: [NOIP 2016 普及组] 回文日期（普及−）：主题是枚举候选，回文判定同样是本模板的子过程。
• luogu P1435: [IOI 2000] 回文字串（普及+/提高−）：不是双指针。最少插入次数 = $n$ 减最长回文子序列，而最长回文子序列就是 $S$ 与 $\text{reverse}(S)$ 的 LCS，属区间 DP / LCS，见 最长公共子序列。
• luogu P3649: [APIO2014] 回文串、luogu P6216: 回文匹配、luogu P1872: 回文串计数（省选及以上）：回文算法题，正解是 Manacher / 回文自动机 / 哈希，双指针只能拿到最暴力的分数。

7.4 这一节的易错点

• i < j 还是 i <= j：判整串回文用 i < j；如果题目要求"每对都要相等"且长度可能为奇数，中心那一位要单独想清楚，别顺手多比一次。
• 下标从 0 还是从 1 开始：模板里两种都给了（string 版从 0、数组版从 1），混用时最容易错的是 j = size()-1 与 j = n 的区别。
• 答案的类型：涉及长度累加的题（比如 P17828）答案能到 $10^{14}$，int 会静默溢出。
• 不要构造长串：压缩输入、$L$ 达 $10^{14}$ 的题，一律让指针走"段"或走"下标区间"，不要 string 拼接。
• 字符集：'a' 与 'A' 是不同字符；判回文前是否统一大小写、是否忽略非字母，要按题意来，别想当然。

8 相关题解

暂无相关题解