题目描述

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

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

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

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

数据范围
1≤n≤100000
输入样例：

5
1 2 2 3 5

输出样例：

3

算法1（双指针）

思路

1.准备i,j两个指针

2.i走在前面，每次走一步，j检查[j,i]有无重复元素,有的话一直往前走(不超过i)

3.每次j走完后即[j,i]区间无重复元素，可更新最长区间

关于判断重复：用计数数组即可,i走一步s[a[i]]++; j走一步,s[a[j]]–
i,j都是当前位置先计数在往后走

时间复杂度

$O(n)$

Java 代码

import java.util.*;

public class Main {
    private static int N = 100010;
    private static int[] a = new int[N];
    private static int[] s = new int[N];
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 0;i < n;i++){
            a[i] = scanner.nextInt();
        }
        int res = 0;
        for(int i = 0,j = 0;i < n;i++){
            //s[a[i]]不要误写成s[i]
            s[a[i]]++;
            while(s[a[i]] > 1){
                //这里先计数,j再往后走
                s[a[j]]--;
                j++;
            }
            res = Math.max(res,i - j + 1);
        }
        System.out.println(res);
    }
}