C++算法题 #15 最长连续不重复子序列

90 阅读 0 评论 60 点赞

我是靠谱客的博主着急烤鸡，最近开发中收集的这篇文章主要介绍C++算法题 #15 最长连续不重复子序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

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

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

数据范围
1≤n≤105
输入样例：

5
1 2 2 3 5

输出样例：

思路
本体的思路是用双指针算法将原本使用朴素算法需要时间复杂度为O(n^2)的算法优化到时间复杂度O(n)。

然后本体的具体过程：
在这里插入图片描述
代码示例

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, res = 0;

int a[N], s[N];


int main()
{
	cin >> n;
	
	for(int i = 0; i  < n; i ++) cin >> a[i];
	
	for(int i = 0, j = 0; i < n; i ++)
	{
		s[a[i]] ++;
		
		while(s[a[i]] > 1) 
		{
			s[a[j]] --;
			j ++;
		}
		res = max(res,i - j + 1);
		
	}
	
	cout << res << endl;
	
	return 0;
}