Jessica's Reading Problem(POJ3320【尺取法】)

Jessica's a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.

A very hard-working boy had manually indexed for her each page of Jessica's text-book with what idea each page is about and thus made a big progress for his courtship. Here you come in to save your skin: given the index, help Jessica decide which contiguous part she should read. For convenience, each idea has been coded with an ID, which is a non-negative integer.

Input

The first line of input is an integer P (1 ≤ P ≤ 1000000), which is the number of pages of Jessica's text-book. The second line contains P non-negative integers describing what idea each page is about. The first integer is what the first page is about, the second integer is what the second page is about, and so on. You may assume all integers that appear can fit well in the signed 32-bit integer type.

Output

Output one line: the number of pages of the shortest contiguous part of the book which contains all ideals covered in the book.

Sample Input

5
1 8 8 8 1

Sample Output

2

题目大意：一本书，每一页都有知识点，知识点可能重复，问：一个最小的，能把所有知识点都包含的连续区间有多大？

思路：建立一个《知识点，次数》的映射，采用尺取法去遍历，初始化区间两头端点为0，若当前区间已经包含所有知识点，则左端点++，若当前区间没有包含所有知识点，右端点++。

那么、如何判断当前区间有没有包含所有的知识点呢？每次想要查询都去遍历一遍映射显然是不现实 的，我们定义一个计数器，设定其初值为1（刚开始的区间大小为1，因为左端点和右端点都指向0），映射的知识点包含次数减1后变成了0（从有到无），则计数器减一，若知识点加一后变成了1（从无到有），则计数器加一

每次区间满足条件后，尝试更新最小区间的大小

#include<iostream>
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
map<long long ,int >m;  //知识点编号和其个数的映射 
long long a[1000010];
int n;
int main() {
	cin>>n;
	for(int i=0; i<n; i++) {
		scanf("%lld",&a[i]);
		m[ a[i] ]=0;
	}
	int l=0,r=0,cunt=1,re=1000010;  
	m[ a[0] ]=1;  //初始区间为 a[0] 
	while(r!=n) {
		if(cunt!=m.size()) { //cunt为当前区间的知识点个数，m为总知识点个数 
			r++;
			m[ a[r] ]++;
			if(m[ a[r] ]==1)cunt++;  //如果该知识点是新知识点 
		} else {
			re=min(re,r-l+1);
			m[ a[l] ]--;
			if(m[ a[l] ]==0)cunt--; 
			l++;
		}
	}
	cout<<re<<endl;
	return 0;
}