题目描述
给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数(均在 0∼105 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
样例
5
1 2 2 3 5
输出样例
3
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int res = 0;
for (int i = 0, j = 0; i < n; i ++ )
{
s[a[i]] ++ ;//a[i]出现的次数
while (j < i && s[a[i]] > 1) //条件成立的话说明有重复的数字出现
//j <= i也行,最坏的情况是:a[i]==s[j],两个连续相同的数字
//因为当j == i的时候循环已经在j+1==i的时候由另外一个条件跳出去了,相当于=没用
{
s[a[j ++ ]] -- ;//j++ 寻找是哪一个位置出现重复数字,追i
}
//j仅仅靠上面的while循环更新就够了,在视频中y总说过,它是有规律的,有点集合中包含与被包含的意思
//j恰巧是while循环跳出来的必要条件
res = max(res, i - j + 1);//没有包含a[j]这个位置上的,a[j]这个位置上的数是重复的元素
//printf("%d %d %d\n",j,i,res); //通过打印这个语句我们会发现,j能找到位于后面的重复元素
}
cout << res << endl;
return 0;
}