【简单】最长连续不重复子序列

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

输入格式

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

输出格式

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

数据范围

{rm{1}} le {rm{n}} le {rm{100000}}

输入样例

代码语言：javascript复制

5
1　2　2　3　5

输出样例

代码语言：javascript复制

3

题解

(双指针）O(n)

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

C 代码

代码语言：javascript复制

#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;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

c++ 指针

0 人点赞