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

Akari2024-03-022024-03-02

AcWing 799. 最长连续不重复子序列 - AcWing
AcWING 799. 最长连续不重复子序列 - 视频评论区
 AcWing 799. 最长连续不重复子序列 - 糖豆爸爸 - 博客园
 最长连续不重复子序列 - 最清晰图解适合新手小白食用-CSDN博客

AcWing 799. 最长连续不重复子序列 [简单] *

1 题目描述

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

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

第二行包含 n 个整数（均在 0 ∼ 10^5 范围内），表示整数序列。

输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围
1 ≤ n ≤ 10^5

输入样例：

5
1 2 2 3 5

输出样例：

3

2 解题思路

2.1 朴素思路

for(int i = 1; i <= n; i ++ )
   for(int j = i; j <= n; j ++ )
        check(i, j); //看看 i - j 之间是不是存在某些数值重复

因为要执行双重循环，所以时间复杂度是 O(N^2) , 要想办法来优化它

2.2 双指针 (滑动窗口 + 桶计数)

说白了就是 : 双指针优化找单调性.

设置双指针 i 和 j, s[ ] 数组表示从 i 到 j 之间各个数字出现的次数，若 s[a[i]] > 1 则说明出现重复数字, 需要移动指针 j .
res 为最长字串长度, 计算公式为 res = max(ans, i - j + 1)

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
int a[N];   // 原数组
int s[N];   // 记个数的桶

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    
    int res = 0;    // 子序列长度 || 滑动容器长度
    for (int i = 0, j = 0; i < n; i ++ ){
        s[a[i]] ++ ;
        
        while (s[a[i]] > 1 ) s[a[j ++ ]] -- ;   // 如果因为 a[i] 的加入, 导致桶中 a[i] 的数量大于 1
        // 也就是有了重复, 则需要从窗口左侧尝试去掉一个, 看看情况会不会变好
        res = max(res, i - j + 1);      // 不断刷新滑动容器长度
    }
    cout << res << endl;
    
    return 0;
}

3 Q & A

3.1 滑动窗口 + 桶计数的具路讲解

先用暴力做, 然后去看有没有单调性, 有就可以双指针优化.

维持一个窗口, 这个窗口里面保证是没有重复元素的, 窗口大小从 0 开始. 左侧有一个慢指针 j , 右侧有一个快指针 i .
当窗口中没有重复元素时, 快指针向右, 多吃进来一个.
通过桶来判断是不是有重复出现, 如果没有, 则窗口最大长度 ++ .
如果有重复元素出现, 则慢指针不断向右, 直到找出并剔除重复元素, 此时窗口变小.
在窗口快慢指针的作用下, 走完整个数组 i == n , 结束循环.
因为快慢指针只走了一遍数组, 可以视时间复杂度为 O(N), 比两层循环优化太多~

总结:

双指针, 快慢指针, 同向。

3.2 `s[a[j ++ ]] -- ;` 的妙处

就是把 j 所在位置的数的数量 - 1 , 然后 j ++ , j 往后移一位. s[q[i]] 存的是每个 q[i] 的数量

其实就是为寻找下一个子串要做的准备.

3.3 while 循环不需要维护 `j < i`

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int q[N], s[N];
// q 是原数组，s 用来记录区间内元素的数量，注意这两个 N 不是一个意思
// 第一个是数组的长度，第二个是数组元素的范围

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> q[i];

    int res = 0;
    // 维护一个区间
    for(int i = 0, j = 0; i < n;  i++ )
    {
        s[q[i]]++;      // 向右扩展区间右端点
        // 当扩展完区间右端点之后, 有可能这个元素 q[i] 会有重复, 下面这个 while 循环就是用来去除重复
        // 去重只有一个办法, 就是收缩区间左端点, 同时收缩时要保证 j < i
        while(j < i && s[q[i]] > 1) s[q[j ++ ]] --;     // 区间数量减 1 , 之后区间断点右移
        // 完成上述扩展和收缩之后, 该区间是一个满足要求的区间, 记录一下长度
        res = max(res, i - j + 1);
    }
    cout << res << endl;

    return 0;
}