双指针算法:一般把有单调性质的序列(满足:(循环顺序从左开始,右则相反)小段性质不满足,左扩大段性质肯定不满足)从暴力o[N2]的复杂度降到o[N]
一般双指针算法板子:
for(int i=0,j=0;i<n;i++){右指针向前
while(j<=i&&条件不满足) 左指针向前j++;
} #include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,a[N],num[N];
int main(int argc, char** argv) {
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int ans=0;
//双指针算法
for(int i=0,j=0;i<n;i++){
num[a[i]]++;//类似桶排序(小数用哈希) ,记录a[i]在现在的子序列里有多少
while(j<=i&&num[a[i]]>1) num[a[j++]]--;
ans=max(ans,i-j+1);
}
printf("%d\n",ans);
return 0;
} 
京公网安备 11010502036488号