双指针¶
前置知识¶
基础算法
what¶
双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。
双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。
why¶
维护区间信息
如果不和其他数据结构结合使用，双指针维护区间信息的最简单模式就是维护具有一定单调性，新增和删去一个元素都很方便处理的信息，就比如正数的和、正整数的积等等。
（“维护”的意思是使用某些数据结构记录一些信息，使其符合一定的性质，并且对这些信息进行增删改查）
双指针算法本质是使用队列维护一个符合条件的区间。
右指针增加相当于入队，左指针增加相对于出队。
一般情况下，这个区间是一个左闭右开区间，[l, r)。
How¶
例题，A-B 数对 - 洛谷¶
题意，给出一串正整数数列以及一个正整数C，要求计算出所有满足 A−B=C 的数对的个数
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, c;
int main(){
cin >> n >> c;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
int l = 1, r = 1;
long long sum = 0;
// a[l] - a[i] < c, 跳出循环的时候，l是第一个满足a[l] - a[i] >= c的
// a[r] - a[i] <= c, 跳出循环的时候，r是第一个不满足a[r] - a[i] <= c的
// 那么此时，r - 1是最后一个满足式子 a[r] - a[i] <= c的
// 满足特定条件的区间是 [l, r)
for (int i = 1; i <= n; i++) {
while (a[l] - a[i] < c && l <= n) l++;
while (a[r] - a[i] <= c && r <= n) r++;
if (a[l] - a[i] == c && a[r - 1] - a[i] == c) {
sum += r - l;
// printf("---%d %d %d\n", a[i], l, r);
}
}
cout << sum << '\n';
return 0;
}
例题，逛画展 - 洛谷¶
题意，找到一个区间覆盖了1~m的所有数，区间尽可能短
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], n, m;
map<int, int> mp;
// [l, r)
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int l = 1, r = 1, num = 0;
int ret = 2e9, x, y;
while (l <= r && r <= n + 1) {
if (num < m) {
r++;
mp[a[r - 1]]++;
if (mp[a[r - 1]] == 1) num++;
}
else {
if (r - l < ret) {
ret = r - l;
x = l, y = r - 1;
}
mp[a[l]]--;
if (mp[a[l]] == 0) num--;
l++;
}
}
cout << x << ' ' << y << '\n';
return 0;
}
题单¶
CF252C Points on Line(难)（题解，ZqIceberg：CF252C_Points on Line）
总结¶
双指针，又名尺取法，英文two pointers。虽然在CCF大纲中我没有找到这个，但在算法比赛中是高频算法。
参考¶
《深入浅出程序设计竞赛》进阶篇