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

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

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

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

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

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

5
1 2 2 3 5
1
2

输出样例：

3
1

思路
本体的思路是用双指针算法将原本使用朴素算法需要时间复杂度为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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33