散列的简单思想

散列是常用算法之一，思想上是以空间为代价来使时间复杂度降低。
举个例子，给出两个整数N,M，再输入N个整数和M个整数，设N={8，3，7，6，2}，M={7，4，2}，欲查询M中元素是不是都再N中出现的个数。

#include<cstdio>
const int maxn=100010;
int hash[maxn]={0};
int main(){
	int n,m,x;
	scanf("%d%d",&n,&m);
	for(int i=0,i<n;i++){
		scanf("%d",&x);
		hash[x]++;
	}
	for(int i=0;i<m;i++){
		scanf("%d",&x);
		if(hash[x]>0)printf("%d",hash[x]);
		else printf("no"); 
	}
	return 0;
}

如果按一般思路遍历所有N中的元素，那么它的时间复杂度就为O(NM),而用这种散列的思想的时间复杂度为O(N+M)。