学习笔记：双指针

· · 算法·理论

双指针

引入

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

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

实现

首先来看一道题。

洛谷 P1102 A-B 数对

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

一眼暴力秒切。于是很快写了出来……

#include <iostream>
#define MAXN 200005
using namespace std;
int n, c, ans;
int a[MAXN];
int read(){
    int t = 1, x = 0;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
    while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * t;
}
int main(){
    n = read();c = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= n ; j ++)
            if(a[i] - a[j] == c)ans++;
    cout << ans << endl;return 0;
}

然而不出意外的话还是出意外了……

注意到数据范围：

对于 75\% 的数据，1 \leq N \leq 2000。

对于 100\% 的数据，1 \leq N \leq 2 \times 10^5，0 \leq a_i <2^{30}，1 \leq C < 2^{30}。

显然，O(n^2) 的暴力是会寄的。考虑一种更加优的做法。

一眼双指针。

我们首先将整个数列排序，之后容易发现对于每一个数 B，与之对应的 A 都是一段连续的区间。

然后我们再考虑如何去找到这个区间。

显然是要找到这个连续区间的左端点和右端点。

考虑到排序之后序列的有序性，我们枚举每个数，他们的左端点和右端点都是单调不降的，因此我们可以用双指针来维护这个东西。

具体地，我们维护这个指针。

首先维护 r1：将 r1 移动到目标区间左侧。

接着维护 r2：将 r2 移动到目标区间右侧。

最后统计：当前答案为 r2-r1。

#include <iostream>
#include <algorithm>
#define int long long
#define MAXN 200005
using namespace std;
int n, c, l, r1, r2, ans;
int a[MAXN];
int read(){
    int t = 1, x = 0;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
    while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * t;
}
signed main(){
    n = read();c = read();
    for(int i = 1 ; i <= n ; i ++)a[i] = read();
    sort(a + 1, a + n + 1);
    l = 1, r1 = 1, r2 = 1;
    while(l <= n){
        while(r1 <= n && a[r1] - a[l] <= c)r1++;
        while(r2 <= n && a[r2] - a[l] < c)r2++;
        if(a[r2] - a[l] == c && a[r1 - 1] - a[l] == c && r1 - 1 >= 1)   
            ans += r1 - r2;
        l++;
    }
    cout << ans << endl;return 0;
}

然后就切了……