算法1
(双指针) $O(n)$
时间复杂度
O(n)
参考文献
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n= sc.nextInt();
int m= sc.nextInt();
//记录打中气球的情况
int arr[]=new int[n];
//记录每种气球打中的个数
int ball[]=new int[m+1];
//记录不同的气球数
int unique=0;
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
int left=0,right=0,min_sh=Integer.MAX_VALUE;
while(right<n){
int cur=arr[right];
if(cur==0){
right++;
continue;
}
if(ball[cur]==0){
//记录当前的气球数有没有用过
unique++;
}
ball[cur]++;
if(unique==m){
while(left<=right && unique==m)
{
min_sh=Math.min(min_sh,right-left+1);
if(arr[left]==0){
left++;
continue;
}
ball[arr[left]]--;
if(ball[arr[left]]==0){
unique--;
}
left++;
}
}
right++;
}
System.out.println(min_sh==Integer.MAX_VALUE?-1:min_sh);
}
}