本文最后更新于 570 天前,其中的信息可能已经有所发展或是发生改变。
思想:
- 双指针。
- 快指针
i
作为某一连续最长不重复区间的右端点,慢指针j
作为该区间的左端点; - 遍历数组
a[i]
,用vis[a[i]]
标记当前区间已经存在的数。 - 当
vis[a[i]] > 1
时:- 说明当前区间存在重复数字,则
j
不断右移,期间vis[a[j]] --
,直到vis[a[i]] == 1
为止; - 此时不含重复数字的区间长度即为
i - j + 1
,用res
来维护最长的区间长度。
- 说明当前区间存在重复数字,则
- 否则说明当前区间还未存在重复数字,
i
持续右移。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int a[N];
int vis[N];
void solve(){
int n; cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
int res = 0;
for(int i = 0, j = 0; i < n; i ++){
vis[a[i]] ++;
while(vis[a[i]] > 1 && j < i){
vis[a[j]] --;
j ++;
}
res = max(res, i - j + 1);
}
cout << res << endl;
}
int main(){
solve();
return 0;
}