【算法】双指针法-526互联

还记得A-B=C问题吗？在之前，我们把原序列排好序，然后变成A=B+C问题，枚举每一个元素作A，然后再序列里如果存在B+C，必然是连续的一段（一个也是），我们利用二分法以O(logN)的时间复杂度获得左右边界相减即可。现在介绍另一种方法：双指针法。

如上面说的，序列里如果存在B+C，必然是连续的一段。维护两个指针，左指针l和右指针r，使得s[l]是首个大于等于B+C的数，s[r]是首个大于B+C的数，这样，s[l]到s[r-1]都是等于B+C的数字，故等于B+C的数字共有r-l个，累加到ans里。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e5 + 10;
int n , c;
int a[N];

int main () 
{
	cin >> n >> c;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	sort(a + 1 , a + 1 + n);
	int l = 1, r1 = 1 , r2 = 1;
	ll ans = 0;
	for(l = 1 ; l <= n ; l ++) {
		while(r1 <= n && a[r1] - a[l] <= c) r1 ++;  //首个大于B+C的下标
		while(r2 <= n && a[r2] - a[l] < c ) r2 ++;  //首个大于等于B+C的下标
		if(a[r2] - a[l] == c && a[r1 - 1] - a[l] == c && r1 - 1 >= 1) 	
			ans += r1 - r2;
	}
	cout << ans;
	return 0;
}

双指针算法本身的时间复杂度是O（n）。

双指针法本质是使用队列去维护一个符合条件的区间，右指针增加相当于入队，左指针增加相当于出队

来这里复习以下快速排序，一样也用到了两个指针维护区间

快速排序

 void Quick_sort (int arr[], int left, int right) {
    if (left >= right) {
        return;
    } //递归结束条件
    int Base_Value = arr[(left+right)/2]; //选择基准值
    int i = left - 1;
    int j = right + 1;

    while (i < j) {
        do
            i++;
        while (arr[i] < Base_Value);
        do
            j--;
        while (arr[j] > Base_Value);

        if (i < j)
            swap(arr[i], arr[j]);
    }
    Quick_sort (arr, left, j); //继续排左边的
    Quick_sort (arr, j + 1, right); //继续排右边的
}

例题2：

2816. 判断子序列 - AcWing题库

太简单了，直接看代码吧

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];

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

	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int j = 0; j < m; j++)
		cin >> b[j];

	int i = 0;

	for (int j = 0; j < m; j++) {
		if (i < n && a[i] == b[j])
			i++;
	}
	if (i == n)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}

总之：双指针算法的核心思想，运用某些单调性质将N方的朴素算法优化成N
此时每个指针遍历数字的次数不超过n先思考暴力做法，再思考双重循环中（暴力一般是两个for循环）的单调关系，得到优化做法。

一般模版如下：

for (int l = 0, r = 0; r < n; ++r)
{
	while (l < r && check(l, r)) ++r;
	// 每道题的具体逻辑
}