首页 > 其他分享 >最长连续不重复子序列

最长连续不重复子序列

时间:2022-12-18 15:33:07浏览次数:40  
标签:Scanner int 重复子 重复 序列 new 最长

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

输入:第一行包整数 n,第二行包含n个整数(均在 0∼100000范围内),表示整数序列。

输出:最长的不包含重复的数的连续区间的长度。

思路:双指针。对于每一个 i,(j,i)表示以 q[i] 结尾的最长连续不重复序列,长度为 i-j+1。由(j,i)已经是不重复序列,因此(j,i+1)要么是不重复序列,要么重复的元素是 q[i+1]。重复的元素是q[i+1]时,只需要找到(j,i)中与 q[i+1] 相等的元素的下标k,就可以更新双指针为(k+1,i+1)。用另一个数组s储存在当前区间(j,i)内每个元素出现的次数,当 s[q[i+1]]>1 时说明(j,i+1)中有重复的数,此时前进 j 指针寻找重复元素。

时间复杂度:O(n)。

 

import java.util.Scanner;
import java.lang.Math;
class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int[] q=new int[n];
        int[] s=new int[100001];
        int r=0;
        for(int i=0;i<n;i++){
            q[i]=scanner.nextInt();
        }
        
        for(int i=0,j=0;i<n;i++){
            s[q[i]]++;
            while(s[q[i]]>1){
                s[q[j++]]--;
            }
            r=Math.max(r,i-j+1);
        }
        System.out.print(r);
    }
}

 

标签:Scanner,int,重复子,重复,序列,new,最长
From: https://www.cnblogs.com/lovxn/p/16990439.html

相关文章