You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2.4 KiB
2.4 KiB
一、题目描述
给定一个长度为 n
的整数序列,请找出 最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 n
。
第二行包含 n
个整数(均在 0∼10^5
范围内),表示整数序列。
输出格式 共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤10^5
输入样例:
5
1 2 2 3 5
输出样例:
3
二、解题思路
1、朴素思路
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
check(i,j); //看看i-j之间是不是存在某些数值重复
因为要执行双重循环,所以时间复杂度是O(N^2)
,下面我们想办法来优化它。
2、滑动窗口+桶计数
-
维持一个窗口,这个窗口里面保证是没有重复元素的,窗口大小从
0
开始。左侧有一个慢指针j
,右侧有一个快指针i
。 -
当窗口中没有重复元素时,快指针向右,多吃进来一个。
-
通过桶来判断是不是有重复出现,如果没有,则窗口最大长度++。
-
如果有重复元素出现,则慢指针不断向右,直到找出并剔除重复元素,此时窗口变小。
-
在窗口快慢指针的作用下,走完整个数组
i==n
,结束循环。 -
因为快慢指针只走了一遍数组,可以视时间复杂度为
O(N)
,比两层循环优化太多~
总结
双指针,快慢指针,同向。
3、C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N]; // 原数组
int s[N]; // 记个数的桶
int res;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, j = 1; i <= n; i++) {
s[a[i]]++; // a[i]这个数在桶中的个数+1
while (s[a[i]] > 1) s[a[j++]]--; // 如果因为a[i]的加入,导致桶中a[i]的数量大于1
// 也就是有了重复,则需要从窗口左侧尝试去掉一个,看看情况会不会变好
// 不断刷新滑动容器长度
res = max(res, i - j + 1);
}
printf("%d\n", res);
return 0;
}