算法1

滑动窗口 $O(n)$

Java 代码

//维护一个窗口，若满足条件，则与最好的窗口做对比，只需遍历一次，时间复杂度n
import java.io.*;
import java.util.*;

public class Main{
    static BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer=new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] set=new int[2002];
    static int[] a=new int[1000005];
    static int hh=0;
    static int tt=-1;
    static int cnt=0;
    public static void main(String args[]) throws IOException{
        //input
        String[] s1=reader.readLine().split(" ");
        int n=Integer.parseInt(s1[0]);
        int maxa=0,maxb=n-1;
        int m=Integer.parseInt(s1[1]);
        String[] s=reader.readLine().split(" ");
        for(int i=0;i<n;i++){
            a[i]=Integer.parseInt(s[i]);
        }
        //
        for(int i=0;i<n;i++){
            //如果出现新画家，窗口移动到i，然后紧凑队头，最后看是否满足
            if(set[a[i]]==0){
                for(int j=tt+1;j<=i;j++){
                    if(set[a[j]]++==0)cnt++;
                }
                tt=i;
                //紧凑队头
                while(set[a[hh]]>1){set[a[hh]]--;hh++;}
                //若新窗口满足与max比较，并主动弹出队头，搜索下一个,总搜索复杂度在on
                if(cnt==m){
                    if(tt-hh<maxb-maxa){maxa=hh;maxb=tt;}
                    set[a[hh]]--;hh++;cnt--;
                }
            }
        }
        //output
        writer.write((maxa+1)+" "+(maxb+1));
        writer.flush();
        writer.close();
        reader.close();
    }




}