最长连续不重复子序列

题目描述

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

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

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

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

数据范围 1≤n≤105

样例

输入样例： 5 1 2 2 3 5 输出样例： 3

算法

双指针 $O(n^2)O(n^2)$

时间复杂度

O(n)

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

//q是原数组，s用来记录区间内元素的数量，注意这两个N不是一个意思
//第一个是数组的长度，第二个是数组元素的范围
int q[N], s[N];
int 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++]] --;//区间数量减一，之后区间断点右移
        //完成上述扩展和收缩之后，该区间是一个满足要求的区间，记录一下长度
        res = max(res, i - j + 1);
    }
    cout << res << endl;

    return 0;
}