双指针法
简述
双指针法，是一种优化技巧，顾名思义，就是通过两个指针维护一段区间的技巧，又名尺取法或\(two-pointers\)。
实现
我们就通过一道例题P1102 A-B 数对体会它的用法。大意就是给定一个长度为\(n\)的序列\(a\)与一个数\(c\)，对于每个元素\(a_i\)，求出有几个\(a_i-c\)，也就是求出所有\(a_i-c=a_j\)的个数。首先，要将序列排序，使其满足单调性，理由是如果序列中存在\(a_i-c\)这个数，那么它的存在一定是连续的，则排序后可以集中统计而不是将整个序列扫一遍。另外需要使用两个指针来维护这个序列。对于左指针\(l\)和右指针\(r\)，满足\(a_l\)是首个大于等于\(a_i-c\)的数，\(a_r\)是首个大于它的数，如此，从\(a_l\)到\(a_{r-1}\)都是等于\(a_i-c\)的数。将\(r-l\)加到答案中即可。
代码如下：
#include <iostream>
using namespace std;
const int N = 2E5 + 5;
int a[N];
int main() {
int n, c;
cin >> n >> c;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);//排序
int l = 0, r = 0;//左右指针
long long sum = 0;
for (int i = 0; i < n; i++) {
while (a[l] < a[i] - c && l < n) l++;//维护左指针
while (a[r] <= a[i] - c && r < n) r++;//维护右指针
if (a[i] - a[l] == c) {
sum += r - l;//统计答案
}
}
cout << sum;
return 0;
}
复杂度分析
双指针法在统计答案过程中可以排除许多无效选项，在整个过程中左右指针都只是从最左端移到了最右端，因此时间复杂度是\(O(n)\)，至于空间复杂度明显是\(O(1)\)。