原题链接:https://www.acwing.com/problem/content/801/
题目分析
用数组记录每个元素出现的次数,遍历以第i个元素为结尾的[i,j]区间的最长长度
显然[i-1,j]必然达到最大,所以每次重复会发生在新增添的a[i]上,j右移直到到达i
和暴力做法的区别就在于指针不会回退
代码细节
每次先把s[a[j]]--,再j++
c++代码
# include <iostream>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main()
{
int n, r = 0;
cin >> n;
for (int i = 0, j = 0; i < n; ++ i)
{
cin >> a[i];
++ s[a[i]];
while (s[a[i]] > 1) -- s[a[j++]]; // 先减次数后右移
r = max(r, i - j + 1) ;
}
cout << r;
return 0;
}
标签:右移,次数,int,重复子,799,cin,++,--,AcWing
From: https://blog.csdn.net/boomgloom/article/details/137143288