最长连续不重复子序列
题目描述
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式 第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式 共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围 1≤n≤105
样例
输入样例： 5 1 2 2 3 5 输出样例： 3
算法
双指针
时间复杂度
O(n)
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
//q是原数组，s用来记录区间内元素的数量，注意这两个N不是一个意思
//第一个是数组的长度，第二个是数组元素的范围
int q[N], s[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> q[i];
int res = 0;
//维护一个区间
for(int i = 0, j = 0; i < n; i++)
{
s[q[i]]++;//向右扩展区间右端点
//当扩展完区间右端点之后，有可能这个元素q[i]会有重复，下面这个while循环就是用来去除重复
//去重只有一个办法，就是收缩区间左端点，同时收缩时要保证j是小于i的
while(j < i && s[q[i]]>1) s[q[j++]] --;//区间数量减一，之后区间断点右移
//完成上述扩展和收缩之后，该区间是一个满足要求的区间，记录一下长度
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
