Tommy Chen home

双指针

22 Sep 2024

1. 简介

双指针是处理数组、字符串和连续区间问题的基础技巧。它用两个下标表示一个区间：左指针 l 和右指针 r，当前窗口就是 [l, r]。

最常见的做法是让右指针不断向右扩展窗口；当窗口不再满足条件时，再让左指针向右收缩窗口。因为两个指针都只会向右移动，所以每个元素最多被右指针访问一次、被左指针移出一次，总时间复杂度通常是 O(n)，而不是枚举所有区间的 O(n²)。

2. 基本思路

假设题目要求在一个数组中寻找满足某个条件的连续区间。双指针维护如下过程：

右指针向右移动，把新元素加入窗口，并更新窗口信息，例如元素和、元素个数或某种出现次数。
如果窗口不满足条件，左指针不断向右移动，把离开的元素从窗口信息中删除。
当窗口重新满足条件时，用当前窗口更新答案。

窗口信息必须能够快速更新。以区间和为例，右端加入 a[r] 时执行 sum += a[r]；左端离开 a[l] 时执行 sum -= a[l]。这样不需要每次重新遍历整个窗口求和。

3. 例子：总时间不超过 T 的最长连续区间

给定每本书的阅读时间 a[i]，总时间不能超过 T，要求最多能连续读多少本书。这个问题的关键是维护当前窗口的阅读总时间 sum。

当右指针加入一本书后，如果 sum > T，说明窗口太长，就不断移走最左边的书，直到 sum <= T。此时窗口 [l, r] 是一个合法区间，可以用它的长度更新答案。

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

const int N = 1000000 + 10;
long long a[N];

int main() {
    int n;
    long long T;
    cin >> n >> T;

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

    int l = 1;
    int answer = 0;
    long long sum = 0;

    for (int r = 1; r <= n; r++) {
        sum += a[r];

        while (sum > T) {
            sum -= a[l];
            l++;
        }

        answer = max(answer, r - l + 1);
    }

    cout << answer;
    return 0;
}

例如阅读时间为 [3, 1, 2, 1, 4]，T 为 5。

右指针扩展到第 3 本书时，窗口为 [3, 1, 2]，总时间为 6，超过限制。
左指针移走第一本书后，窗口变为 [1, 2]，总时间为 3，再次合法。
继续移动右指针，并在每个合法窗口处更新最长长度。

程序中的 while 乍看起来像嵌套循环，但左指针在整个过程中最多从 1 移动到 n 一次。因此左右指针合起来最多移动 2n 次，时间复杂度仍为 O(n)。

4. 适用条件

上面的“区间和不超过 T”写法要求数组元素非负。因为右端加入一个非负数只会让 sum 变大，左端移走一个非负数只会让 sum 变小，窗口是否满足条件才具有单调性。

如果数组中允许负数，加入一个元素后区间和可能反而变小，移走元素后也可能变大，简单的双指针就不一定正确。

同样的窗口思想也可用于字符串和类别统计问题。例如，维护窗口中每种字符的出现次数；当窗口包含所需的所有字符时收缩左端，就能寻找最短的覆盖子串。若题目中的元素没有天然顺序，也可以先按数值或坐标排序，再在排序后的序列上使用双指针。

5. 常见错误

加入右端元素后，忘记立刻更新窗口信息。
收缩左端时，忘记删除 a[l] 对 sum 或计数器的影响。
使用 if 而不是 while：一次收缩后窗口可能仍不合法。
混淆窗口长度：下标从 1 开始时，长度是 r - l + 1。

双指针的重点不是固定模板，而是维护一个始终可解释的窗口：右指针负责尝试扩大答案，左指针负责在条件被破坏时恢复合法状态。先明确窗口条件和需要维护的信息，就能把许多连续区间问题转化为线性扫描。

双指针

Related Posts