搜 索

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

  • 184阅读
  • 2021年06月04日
  • 0评论
首页 / 学习笔记 / 正文

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

输入格式

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

输出格式

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

数据范围

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

输入样例

5
1 2 2 3 5

输出样例

3

题解

(双指针)$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;
}
评论区
暂无评论
avatar
本站由 upyun提供CDN加速/云存储服务