题目描述

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

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

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

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

数据范围
1≤n≤100000
输入样例：
5
1 2 2 3 5
输出样例：
3

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <cmath>
using namespace std;
//本题思路为 对于数组a子序列初始下标为0 最大下标为i
//i不断右移 子序列的长度也不断更新 最大长度根据当前长度更新 
//直到a[i] 与子序列的一个数重复了 
//此时子序列更新 初始下标变成与a[i]重复的那个数的下标+1
//比如a[i] 与a[2] 重复了 子序列初始下标就变成3  
//i继续右移 重复 子序列初始下标更新 ，重复 更新 
//直到遍历完 输出最大长度 
int a[100010],s[100010];
int res;
int main (){
    int n,i,j;
    scanf ("%d",&n);
    for (i = 0;i < n;i++) scanf ("%d",&a[i]);
    for (i = 0,j = 0;i < n;i++){
//j存放子序列初始下标 
        s[a[i]]++;
//s数组存放子序列元素出现次数
//可以快速查询到a[i]是否与子序列内部重复 
        while (j <= i&&s[a[i]] > 1){
//如果重复了 
//那么子序列初始下标就更新到与a[i] 重复的那个数的下标+1 
            s[a[j]]--;
//由于子序列初始下标向右更新 a[j]就不是子序列元素了 不用记录 归0 
            j++;
//初始下标移动到下一个元素 
        }
        res=max(res,i-j+1);
//res记录最大长度 i每次右移都进行子序列长度的更新 
//若大于 当前最大记录 res更新 
    }
    printf ("%d",res);
    return 0;
}