【简单】最长连续不重复子序列
给定一个长度为 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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录