学步园

题目：输入一个乱序数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。
如果有多对数字的和等于输入的数字，输出所有合适的。

使用hash的方法，以空间换时间。

完整代码如下：

#include<iostream>
#include<cstdlib>
using namespace std;
#define N 8
#define M 50//hash

void Search(int a[],int n,int sum)
{
	int i,isum;
	int hash[M]={0,0};//初始化为0
	for(i=0;i<n;i++)
		hash[a[i]]++;
	i=0;
	while(i<=sum/2)//此处减少搜索量
	{
		if(hash[i]==0)
			++i;
		else
		{
			int isum=sum-i;
			if(isum!=i && hash[isum]>0)
			{
				cout<<i<<" "<<isum<<endl;
				++i;
			}
			else if(isum==i && hash[i]>1)
			{
				cout<<i<<" "<<isum<<endl;
				++i;
			}//若两个等值相加
			else ++i;
		}
	}
}
void main()
{
	int a[N]={11,4,9,7,11,1,14,15};
	
	int sum=22;
	Search(a,N,sum);
}