最长连续不重复子序列

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

输入格式

第一行包含整数 $n$。
第二行包含 $n$ 个整数（均在 ${\rm{0}}\sim100000$ 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复数字的连续子序列长度。

数据范围

${\rm{1}} \le {\rm{n}} \le {\rm{100000}}$

输入样例

5
1　2　2　3　5

输出样例

题解

(双指针）$O(n)$

用 $i$指针进行枚举的时候，记录对应数出现的次数，并且 $i$每右移一次，判断一次对应数出现的次数，若超过一次，则移动$j$指针，直到该数出现次数降低为一次，停止$j$指针移动。
每次移动$i$指针都将结果更新为较大的一个，即可实现题目要求。

C++ 代码

#include <iostream>

using namespace std;
//双指针法O(n)
const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    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)  //出现次数大于1则重复
        {
            s[a[j]]--;  //将对应数出现次数减一
            j++;    //往后移动j指针，直到跳过一个重复的元素
        }
        res = max(res, i - j + 1);  //求最大子序列长度
    }
    cout << res << endl;
    return 0;
}

版权属于：字节星球/肥柴之家 （转载请联系作者授权）
原文链接：https://www.bytecho.net/archives/1778.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog