十二.双指针算法

一般只有两大类。一大类是两个指针分别指向两个序列（比如归并排序），另一大类是两个指针指向一个序列（比如快排）。

最核心思想是用来优化。比如有时需要用二重循环来解决的问题，其时间复杂度为O(n²)，用了双指针可以优化到O(n)。

一般的通用模板（这里只是举个例子并不是完全一样的）：

for(i=0,j=0;i<n;i++){
    while(j<i&&check(i,j)) j++;//j不能越界且i，j满足某一条件时
    //接下来每道题的具体逻辑
}

1.最长连续不重复子序列

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

如何记录是否有重复数字？可以开一个大小为N的数组S（N为数据范围），在题目给出的数组a中，每出现一个数a[i],把S[a[i]]++。当指针移动，其离开两指针之间区间时，S[a[i]]--。

维护的标记数组中不能出现重复数字，例如如果 i 向后移动一格，可以分为 2种情况

1. 没有重复数字，此时 j 不需要移动，更新最大长度即可

2. 有重复数字，此时 i 和 j 之间有重复数字，不符合题意，所以需要将 j 向后移动，直到没有重复数字为止

总的来说，两个指针i和j，i放在外面的大循环，从0开始。i里面内置while循环j，当j<i并且check(i,j)时，j++。因为如果移动一个i就出现了重复数字，那重复的必然是i指向的那个数，所以check(i,j)可以写为a[i]！=a[j]。

#include <iostream>
​
using namespace std;
​
const int N=100010;
​
int n;
int a[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++){
        s[a[i]]++;
        while(s[a[i]]>1){//不写其他的判断条件是因为只要满足这一个条件就可以了。如果没有重复数字，说明此时的序列已经满足条件了，不需要再将j往后移动
            s[a[j]]--;
            j++;
        }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    
    return 0;
}

2.数组元素的目标和

给定两个数组和一个目标数x，要求输出两个数组中所有相加值等于x的数对(i,j)

暴力做法：一个嵌套循环分别遍历两个数组，然后输出所有满足的。

思路：因为两个数组都是升序的有序数组，所以假如用i指向第一个数组，当它与j指向的第二个数组中的元素相加总和等于x时，当它再往后指一个数（相当于其指向的数必然变大），则j只能往前指（变小）。