pku3220source.cpp

PKU3220代码 简单HASH的使用

//PKU3220 Source 

#include<iostream>
#include<fstream>

using namespace std;
long cnt;
long pages[1000002];
long flag[1000002];
long hash[148756][12];
long ind[148756][12];
long n;
long nidea;
bool find(long num,long p)
{
	long index=num%148753;
	long i;
	for(i=0;i<=11;i++){
		if(hash[index][i]==num){
			pages[p]=ind[index][i];
			return 1;
		}
		if(hash[index][i]<=0){
			hash[index][i]=num;
			ind[index][i]=cnt;
			pages[p]=cnt;
			return 0;
		}
	}
	return 0;
}
void solve()
{
	long i;
	memset(flag,0,sizeof(flag));nidea=cnt-1;
	long pre=1;long result=1000000;long sum=0;
	for(i=1;i<=n;i++){
		if(!flag[pages[i]]){
			sum++;
			flag[pages[i]]+=1;
		}
		else{flag[pages[i]]+=1;
		}
		if(sum==nidea){
			while(pre<=i&&flag[pages[pre]]>1)
			{
				flag[pages[pre]]--;
				pre++;
			}
			if(i-pre+1<result)
			{
				result=i-pre+1;
			}
		}
	}

	cout<<result<<endl;
}
int main()
{
	//freopen("input.in","r",stdin);

	long i;
	while(cin>>n&&n!=0){
		nidea=0;cnt=1;
		memset(hash,0,sizeof(hash));
		for(i=1;i<=n;i++){
	  	long tmp;
	     	scanf("%ld",&tmp);
			if(tmp==0)
				tmp=698472;
		   if(!find(tmp,i)){
			 cnt++;
		   }
		}
		solve();
	}
	return 0;
}