双指针算法

双指针算法，可以优化一些朴素算法，减少遍历的次数 ，降低算法的时间复杂度。

一般模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ; //指针的移动

    // 具体问题的逻辑
}

常见问题分类：

​ (1) 对于一个序列，用两个指针维护一段区间
​ (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

---

例题： 最长连续不重复子序列

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];						     //s[N]，存储当前序列中各个数字的数量

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int res = 0;
    for (int i = 0, j = 0; i < n; i++)	//双指针， i指针先往前
    {
        s[a[i]]++;						//将这个数加入当前i ，j 之间
        while (s[a[i]] > 1)				//如果数量大于1 ， 那么就是有重复的
        {
            s[a[j]]--;					//将重复的T出去
            j++;						//指针右移，直到与i指针重合了，继续开始下一个序列
        }

        res = max(res, i - j + 1);		//记录当前的最大值
    }
    cout << res << endl;
    return 0;
}

例题：[数组元素的目标和](AcWing 800. 数组元素的目标和 - AcWing)

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i] + B[j] = x A[i]+B[j]= x 的数对 (i,j)(i,j)。

数据保证有唯一解。

求目标和的时候双指针一个指向首位，一个指向末尾

#include <iostream>

using namespace std;

const int N = 100010;

int A[N], B[N];
int n, m, x;

int main()
{
    cin >> n >> m >> x;
    for (int i = 0; i < n; i++)
        cin >> A[i];
    for (int i = 0; i < m; i++)
        cin >> B[i];
    for (int i = 0, j = m - 1; i < n; i++) //一个指向首位，一个指向末尾
    {
        while (j >= 0 && A[i] + B[j] > x)	//先用大数， 太大了就用小数。
            j--;							//把一个数组看成大数序列 ，一个数组看成是小数序列
        if (A[i] + B[j] == x)				//输出答案即可
        {
            printf("%d %d", i, j);
            break;
        }
    }
    return 0;
}