题目描述

最长连续不重复子串

样例

双指针

时间复杂度

最多 2 * O(n)

JAVA代码

import java.util.*;
import java.io.*;

class Main{
    static int [] cnt, q;
    static int n; 

    public static void main(String args[])throws IOException{

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());

        // 映射计数数组
        cnt = new int [n+1];

        q = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();

        int res = 0;

        for(int i=0, j = 0; i< n; i++){
            //映射指针 i
            cnt[q[i]]++;

            //如果计数数组 指针 i > 1; 那么久是重复了
            while(j<i && cnt[q[i]]>1 ){
                //那么j指针从0开始自增, 映射计数指针 自减 
                //直到遇到i重复指针 停职.
                cnt[q[j++]]--;
            }
            res = Math.max(res, i-j + 1);
        }
        System.out.print(res);

    }
}