时间复杂度:$O(n)$,即看j
使用的次数,小于$2n$
算法:i
慢指针,j
快指针
#include <iostream>
using namespace std;
const int MAX = 1e5 + 10;
int a[MAX], b[MAX]; // b 记录出现过的数字
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int j = 0, l = 0;
for (int i = 0; i < n; ++i) {
// 无重复元素的区间[i, j)
for (; j < n && b[a[j]] == 0; ++j)
++b[a[j]];
l = max(l, j - i);
if (j == n)
break;
--b[a[i]];
}
cout << l;
return 0;
}