题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

include[HTML_REMOVED]

using namespace std;
const int N=100010;
int a[N],s[N];
//a[N] 用来存放原有的数字，s[N]用来存放数字出现的次数
int main(){
int n;
cin>>n;
for (int i=0;i<n;i++) scanf(“%d”,&a[i]);

//双指针算法
for (int i=0,j=0;i[HTML_REMOVED]1){ //当出现存在重复数据时，就使用另一个指针将之前的有重复数字的子区间剔除出去。
s[a[j]]–; //判断是否已剔除重复元素
j++; //子区间前进
}
//每次剔除完重复元素，都要进行当前区间的计算.
res=max(res,i-j+1);

}
cout<<res<<endl;
return 0;

}

时间复杂度分析

这样的话，i指针会完整地遍历完整个数组一遍，但j指针只在最坏的情况下，才会将整个数组遍历一遍，时间复杂度仅为O(n)