题目:给定一个长度为 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