题目描述

原题

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

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

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

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

数据范围

1≤n≤100000

输入样例：

5
1 2 2 3 5

输出样例：

3

算法：双指针

定义两个指针变量i，j，i不断累加往后走，每出现一个数记录一次，当出现重复数字的次数大于1，那么就让j也开始走，
在这个过程中，记录数出现几次的次数开始减少，当i那个位置的数字出现次数不大于1的时候，j才停止，i继续往后遍历
。如此循环，直到遍历完整个序列
（具体情况看代码注释详解）

时间复杂度

O（n)

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//a原数组 s：记录每一个数字出现的次数，
//s[i]=1,i表示是数字几，1表示这个数字出现了一次（这里是重点，下面会用到）
int a[N] , s[N];
int n ; 

int main(){
    cin>>n;
    //输入原数组
    for(int i = 0 ; i < n ; i++)cin>>a[i];
    //记录答案的
    int res = 0;
    //开始循环遍历，定义两个指针变量i，j，i在前，j在后
    for(int i = 0 , j = 0 ; i < n ; i++){
        //a[i]出现，就加1
        s[a[i]] ++;
        /*
        当j还没有超过i，并且a[i]这个数出现超过了一次，那么此时就需要移动
        j的位置，直到（i，j）这个范围内a[i]这个数只出现过一次，j才会停下
        注意数字出现的次数是从a[j]位置开始减的，因为你不知道重复的那个数
        字是在最新i的前面一个还是前面几个。最后指针j开始更新位置，往前走
        */
        while(j < i && s[a[i]] > 1){
            s[a[j]] --;
            j++;
        }
        //处理完重复的数字之后，我们就要更新答案，之前记录的值和当前
        //（i，j）这个长度，到底谁大，取大的值
        res = max(res, i - j + 1);
    }
    //循环遍历结束之后，那么也就找到了答案。
    cout<<res<<endl;
    return 0;
}