Jessica's Reading Problem——POJ3320

Jessica's Reading Problem——POJ3320

题目大意：

Jessica 将面临考试，她只能临时抱佛脚的在短时间内将课本内的所有知识点过一轮，课本里面的P个知识点顺序混乱，而且重复。

要求找出课本的连续页数，这些页数满足：包含全部知识点，且是包含全部知识点的页数区间里面最短的。

尺取法解题。

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner reader=new Scanner(System.in);

        int P=reader.nextInt();

        Integer array[]=new Integer[P];

        HashSet set=new HashSet();

        for(int i=0;i<P;i++){

            array[i]=reader.nextInt();

            set.add(array[i]);

        }

        int n=set.size();    //知识点个数

        int s=0;    //开始结点

        int e=0;    //结束结点

        int num=0;    //统计目前知识点个数

        int res=P;

        HashMap map=new HashMap();

        while(true){

            while(e<P && num<n){

                if(map.containsKey(array[e])==false){    //尚未包含此知识点

                    map.put(array[e], 1);    //放入此知识点

                    num++;

                }else{

                    Integer newValue=(Integer)map.get(array[e])+1;    //旧知识点

                    map.put(array[e], newValue);

                }

                e++;

            }

            if(num<n){

                break;

            }

            res=Math.min(res,e-s);

            Integer newValue=(Integer)map.get(array[s])-1;

            map.put(array[s], newValue);

            if((Integer)map.get(array[s])==0){    //开始结点的知识点数<=1时，减去开始结点后知识个数会减少

                map.remove(array[s]);

                num--;

            }

            s++;    //开始结点自增

        }

        System.out.print(res);

    }

}