最长连续不重复子序列

题目

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

输入格式
第一行包含整数n。第二行包含n个整数（均在0~100000范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。

数据范围
1≤n≤100000

输入样例：
5
1 2 2 3 5
输出样例：
3

分析

这个题的题意是要求出一个数组中最长的且连续不重复的子序列。如果暴力的话会是一个O(n^2)的复杂度。

可以用双指针来做，首先一个指针 i 来表示右端点，指针 j 来表示左端点，当指针 i 向右移动时，指针 j 只能向右移动或者不移动，这样就有了单调性，就可以用双指针来做。因为这个题的数据范围，所以可以开一个数组来记录每一个数字出现了几次，如果数据范围特别大的话，可以用pair，map来做。
i 指针从左到右移动，然后 j 也是从左到右，如果aa[ i ]出现过 j 指针就向右移动一位，同时这个数出现次数减 1，然后求序列的长度取max

代码

#include<iostream>
#include<algorithm>
using namespace std;
int aa[123456];
int bb[123456];

int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>aa[i];
    for(int i=1,j=1;i<=n;i++)
    {
        bb[aa[i]]++;
        while(j<i&&bb[aa[i]]>1) bb[aa[j++]]--;//这个需要写成while，不能写成if
        ans=max(ans,i-j+1);
    }
    cout<<ans<<endl; 
    return 0;
}