[编程笔记]-Two_Pointers双指针

前言

最近时间紧迫，从这篇文章开始，就着重记笔记了，不再提供详细教程。

简介

双指针算法，名义上说就是使用两个指针循环（一个或多个）数组，但实际上通常用不到指针。

一般情况下，双指针算法用于特定情境，将O(n²)的时间复杂度简化成O(n)。

模板

一般情况下，形如下方所示的代码，在满足特定需求的情况下，都可以转化成双指针来做。

for(int i=0;i<n;i++){
	for(int j=0;j<=i;j++){
		if(check(i,j)){
			//功能代码
		}
	}
}

转化成：

for(int i=0,j=0;i<n;i++){
	while(check(i,j)){
		j++;
	}
	//功能代码
}

例题

AcWing799-最长连续不重复子序列

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,ans;
int a[N],s[N];

int main(){
    scanf("%d",&n);
    for(int i=1,j=1;i<=n;i++){
        scanf("%d",&a[i]);
        s[a[i]]++;
        while(s[a[i]]>0){
            s[a[j++]]--;
        }
        ans=max(ans,i-j+1);
    }
    printf("%d",ans);
    return 0;
}

完结撒花o(￣︶￣)o