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

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 799. 最长连续不重复子序列

一、题目描述

给定一个长度为 n 的整数序列,请找出 最长的不包含重复的数的连续区间,输出它的长度。

输入格式 第一行包含整数 n

第二行包含 n 个整数(均在 010^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;
}