超时做法,思路是可以的
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
/*
分析:创建一个辅助数组b[N],表示每个数访问过的次数,
如果为0,则设置为1,如果非0,则说明有重复的数,
将当前长度l记录,最后输出最长的l
*/
int main(){
int n, a[N],l = 0, lmax = 0;
vector<int> b(N, 0);
cin >> n;
for(int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = 0; i < n; i ++ ){
for(int j = i; l + n - j > lmax ; j ++ ){
//cout << j << ' ';
//cout << a[j] << '-' << b[a[j]] << endl;
if(b[a[j]] != 1){
b[a[j]] = 1;
//cout << b[a[i]] << '-' << i << ' ';
l++;
}
else if(b[a[j]] == 1){
j = i;
break;
}
}
//for(int z = 0; z < n ; z++) b[a[z]] = 0;
fill(b.begin(), b.end(), 0);
if(l > lmax) lmax=l;
l=0;
//cout << l << '~' << lmax << ' '<< i << ' '<< endl;
}
cout << lmax;
return 0;
}
双指针优化算法
#include <iostream>
using namespace std;
const int N = 100010;
/*
全局,静态变量,一般默认为0;
局部变量在栈上,取决于此处原来的数据,如果不初始化的话;
动态变量在堆上.
*/
int n;
int a[N],s[N];
int res=0;
int main(){
cin >> n;
for( int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = 0, j = 0; i < n; i ++ ){
s[a[i]]++;
while(s[a[i]] > 1){
s[a[j]]--;
j++;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}