双指针算法:一般把有单调性质的序列(满足:(循环顺序从左开始,右则相反)小段性质不满足,左扩大段性质肯定不满足)从暴力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; }