双指针 - LRY的技术分享站

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。

双指针不能算一个真正意义上的算法，而是一种编程技巧，一种解决问题的优化思路

这里介绍两种比较常用的双指针的应用场景：维护区间信息和利用序列有序性

维护区间信息

P1147 连续自然数和 - 洛谷

对一个给定的正整数 $M$，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 $M$。

例子：$1998+1999+2000+2001+2002 = 10000$，所以从 $1998$ 到 $2002$ 的一个自然数段为 $M=10000$ 的一个解。

题目分析

由于我们需要考虑一段连续的整数段，所以我们可以用两个指针，一个指向区间的开头，一个指向区间的末尾，这样就可以表示一段连续的区间了

我们考虑中间过程，假设开头指针记为$l$，结尾指针记为$r$，且假设int sum(int l, int r)这个函数实现了求一段连续整数和的功能，则

若$sum(l, r) < M$，则我们应该把区间往右扩，将右指针$r$加一，这样区间和会变大
若$sum(l, r) > M$，则我们应该把区间缩小，将左指针$l$加一，这样区间的下界就会变大，同时减去了最小的那个数
若$sum(l, r) = M$，计入符合条件的答案中

代码实现

int sum(int l, int r) {
    return 1ll * (l + r) * (r - l + 1) / 2;
}
void solve() {
    int m;
    cin >> m;
    int l = 1, r = 1;
    while (r <= m) {
        int s = sum(l, r);
        if (s < m) r ++;
        else if (s > m) l ++;
        else {
            if (r - l + 1 >= 2) {
                cout << l << " " << r << "\n";
                l ++;
            } else {
                r ++;
            }
        }
    }
}

利用序列有序性

P1102 A-B 数对 - 洛谷

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

我们可以先对数据进行一轮从小到大的排序，令左指针$l$指向的数为$B$，右指针$r$指向的数为$A$

当$A - B < C$时，向右移动右指针$r$使得$A$的值扩大，这样$A - B$的值能变大
当$A - B > C$时，向右移动左指针$l$使得$B$的值扩大，这样$A - B$的值能变小
当$A - B = C$时，这个时候处理方式和上面那道题有点不一样，因为题目中说，不同位置的数字一样的数对算不同的数对，则我们要将此时所有的$A$的个数和$B$的个数都统计出来，再讲二者的个数相乘（每个AB都可以两两组合），累加到答案中

int n, c;
int a[N];
void solve() {
    cin >> n >> c;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    std::sort(a + 1, a + n + 1);
    int l = 1, r = 2;
    long long ans = 0;
    while (r <= n) {
        if (a[r] - a[l] < c) r ++;
        else if (a[r] - a[l] > c) l ++;
        else {
            int i = l, j = r;
            while (i < r && a[i] == a[l]) i ++;
            while (j <= n && a[j] == a[r]) j ++;
            ans += 1ll * (i - l) * (j - r);
            l = i, r = j;
        }
    }

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