799. 最长连续不重复子序列（双指针算法）

佚名 6年前 (2020-01-17) 算法 1356人围观抢沙发百度已收录

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

输入格式

第一行包含整数n。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

输出格式

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

数据范围

1≤n≤1000001≤n≤100000

输入样例：

5
1 2 2 3 5

输出样例：

思路：暴力就是枚举所有情况，对于每个右端点，枚举每个左端点，会超时

for(int i=0;i<n;i++）
  for(int j=0;j<i;j++)
     if(check(j,i)
         res=max(res,i-j+1)

用双指针算法，对于每个右端点i，求出最左端点j

for(int i=0,j=0;i<n;i++){
   while(j<=i && check(j,i)) j++;
   res=max(res,i-j+1);
}

具体实现：

import java.util.*;
public class Main{
    static int n;
    static final int max=100005;
    static int a[]=new int[max];
    static int s[]=new int[max];//用s数组记录当前某个数字的数量
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        for(int i=0;i<n;i++) a[i]=scan.nextInt();
        int res=0;
        for(int i=0,j=0;i<n;i++){
            s[a[i]]++;
            while(s[a[i]]>1){//对于当前的右端点，说明有重复数字
                s[a[j]]--;   //左端点向右移动
                j++;
            }
            res=Math.max(res,i-j+1);
        }
        System.out.println(res);
    }
}