poj3320 (尺取法)

n个数，求最小区间覆盖着n个数中所有的不相同的数字。

解题思路：

AC代码：

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Scanner;

import java.util.Set;

public class Main{

	/**

	 * @param args

	 */

	static int n;

	static Set<Integer> set = new HashSet<Integer>() ;

	static int a[]=new int[1000000+2];

	static Map<Integer,Integer> map=new HashMap<Integer, Integer>();

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);

		n=scan.nextInt();

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

            set.add(a[i] = scan.nextInt() ) ;

        }

		int  size = set.size() ;  //计算不同知识点的个数

		int start = 0 , end = 0 , sum = 0 ;

        int res = n ;

        for(;;){

            while(end < n && sum < size){

                Integer cnt = map.get(a[end]) ;

                if(cnt == null){

                    sum++ ;

                    map.put(a[end] , 1) ;

                }

                else map.put(a[end] , cnt+1) ;

                end++ ;

            }

            if(sum < size) break ;

            res = Math.min(end - start , res) ;

            int cnt = map.get(a[start]) ;

            if(cnt == 1){

                map.remove(a[start]) ;

                sum-- ;

            }

            else map.put(a[start] , cnt-1) ;

            start++ ;

        }

        System.out.println(res) ;

	}

}