双指针

双指针又称尺取法，是一种常用的算法技巧，可以用来解决序列的区间问题。

双指针的基本思想：

两个指针 $i,j$ ，有两种扫描方向：

1. 反向扫描：$i,j$ 方向相反，$i$ 从前往后扫描，$j$ 从后往前扫描，在中间相会。
2. 同向扫描：$i,j$ 方向相同，都从前往后扫描，可以让 $j$ 跑在 $i$ 的前面。

同向扫描的两个指针又称为快慢指针，快慢指针在序列上产生一个大小可变的滑动窗口，应用非常广泛。

双指针应用

洛谷 P1147. 连续正整数和

题目描述

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

例如，$1998+1999+2000+2001+2002=10000$，所以从 $1998$ 到 $2002$ 的一个正整数段为 $M=10000$ 的一个解。

输入格式

输入一行一个正整数，表示 $M$ 的值（$10\le M\le 2\times {10}^6$）。

输出格式

输出每行包含两个正整数，表示一个满足条件的连续正整数段的左右端点，两数之间用一个空格隔开。

输出按左端点大小升序排列。

分析

把自然数看作一个升序序列，让 $i$ 指针指向一段数的左端，$j$ 指针指向这段数的右端，$s$ 维护这段数的和，如果 $s<m$，则 $j\mathtt{\text{++}},s\mathtt{\text{+=}}j$；如果 $s\ge m$，则 $s\mathtt{\text{-=}}i,i\mathtt{\text{++}}$。注意当 $s=m$ 时，输出答案。

代码

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

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

    int i = 1, j = 1, s = 1;
    while (i <= n / 2) {
        if (s < n) {
            j++;
            s +=j ;
        } else {
            if (s == n) cout << i << " " << j << endl;
            s -= i;
            i++;
        }
    }

    return 0;
}

洛谷 P1102. A - B 数对

题目描述

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

输入格式

输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 $A-B=C$ 的数对的个数。

分析

将数列升序排序。

设 $k$ 指针负责枚举每一个数字。

$i$ 指针指向满足 $a[i]-a[k]=c$ 的一段数的左端。

$j$ 指针指向满足 $a[i]-a[k]=c$ 的这段数的右端 $+1$ 位置。

枚举 $k$ 并统计答案 $ans=ans+(j-i)$。

代码

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

int n, C, a[200010];

int main() {
    cin >> n >> C;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);

    long long ans = 0;
    int i = 1, j = 1;
    for (int k = 1; k <= n; k++) {
        while (i <= n && a[i] - a[k] < C) i++;
        while (j <= n && a[j] - a[k] <= C) j++;
        ans += j - i;
    }
    cout << ans << endl;

    return 0;
}

洛谷 P1638. 逛画展

题目描述

博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。

游客在购买门票时必须说明两个数字，$x$ 和 $y$，代表他要看展览中的第 $x$ 幅至第 $y$ 幅画（包含 $x,y$）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 $x,y$，数据保证一定有解。

若存在多组解，输出 $x$ 最小的那组。

输入格式

第一行两个整数 $n,m$，分别表示博览馆内的图画总数及这些图画是由多少位名师所绘画的。

第二行包含 $n$ 个整数 $a_i$，代表画第 $i$ 幅画的名师的编号。

输出格式

一行两个整数 $x,y$。

分析

$a[i]$ 表示第 $i$ 幅画的名师编号。

$cnt[i]$ 表示当前区间编号为 $i$ 的名师的图画数量。

$num$ 记录当前区间有多少位画家。

$len$ 记录合法的区间长度。

$l,r$ 记录合法的区间左右端点。

设 $i$ 指针指向当前区间的左端点，$j$ 指针指向当前区间的右端点。

1. 如果当前区间内的画家数量 $num<m$，则 j++; cnt[a[j]]++; if (cnt[a[j]] == 1) num++;
2. 如果当前区间内的画家数量 $num=m$，则比较 $len$ 与当前区间长度，更新 $len$ 与 $l,r$。cnt[a[i]]--; if (cnt[a[i]] == 0) num--; i++;

代码

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

int n, m, a[100010], cnt[2010];

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

    int i = 1, j = 1, num = 1, len = 1e9, l = -1, r = -1;
    cnt[a[1]]++;

    while (j <= n) {
        if (num < m) {
            j++;
            cnt[a[j]]++;
            if (cnt[a[j]] == 1) num++;
        } else if (num == m) {
            if (len > j - i + 1) {
                len = j - i + 1;
                l = i;
                r = j;
            }
            cnt[a[i]]--;
            if (cnt[a[i]] == 0) num--;
            i++;
        }
    }

    cout << l << " " << r << endl;

    return 0;
}