题目描述

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

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

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

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

数据范围
1≤n≤100000

样例

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

算法1

双指针算法

利用某种单调性质可以将朴素做法优化到O(n)
两大类：
1.指向2个区间
2.指向一个区间

时间复杂度

O(n)

python 代码

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    s = [0]*100010          #记录当前j到i区间内，每个元素出现的次数
    ans = 1
    j=0
    for i in range(n):
        s[a[i]] += 1
        while s[a[i]]>1:
            s[a[j]] -= 1
            j+=1
        ans = max(ans,i-j+1)
    print(ans)