接着上面一篇文章： http://blog.csdn.net/u013476464/article/details/40651451

接下来我们拓展一下题目，如果数组是乱序的，并且规定数组中的元素所有为非负整数，相同给定一个数sum，在数组中找出随意两个数，使二者的和为sum。

分析：

由于题目中限定了数组中的元素为非负整数，因此我们能够用哈希数组，开辟一个长度为sum的bool数组B[sum]，并所有初始化为false，对数组A进行一次遍历，假设当前的元素A[i]大于sum，则直接跳过，否则，继续作例如以下推断，假设B[A[i]]为false，则将B[sum-A[i]]置为ture，这样当继续向后遍历时，假设有B[A[i]]为true，则有符合条件的两个数，分别为A[i]和sum-A[i]。假设遍历A结束后依旧没有发现有B[A[i]]为true的元素，则说明找不到符合条件的元素。

该算法的时间复杂度为O（n），但空间复杂度为O（sum）。或者假设知道非负整数数组A的最大值为MAX，则也能够开辟一个MAX大小的bool数组，思路是一样的。

哈希表简单介绍：

哈希表是一种数据结构，它能够提供高速的插入和删除操作。不管哈希表有多少数据，插入、删除仅仅须要接近常量的时间，即 O(1) 的时间级。明显比树还快，树的操作通常须要O(N)的时间级。

缺点：它是基于数组的，数组创建之后难以维护。某些哈希表被基本填满时，性能下降很严重。并且也没有提供一种方法能够以不论什么一种顺序（比如从大到小）遍历表中数据项。

若需把单词当做key（数组下标）获取value（数据），能够把单词分解成字母组合，把字母转化为它们的数字代码（a-1，b-2，c-3……z-26，空格-27），每一个数字乘以相应的27（由于字母有27种可能，包含空格）的幂，然后结果相加，就能够每一个单词相应一个独一无二的数字。

代码：

// offer01.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include "stdio.h"

#include <stdlib.h>

bool FindNumSum(int *A,int len,int sum,int *a,int *b)

{

	if(A==NULL||len<2)

		return false;

	bool *B=(bool*)calloc(sum,sizeof(bool));//定义长度为sum的bool型数组

	if(B==NULL)

	  {

		exit(EXIT_FAILURE);

	  }

	for(int i=0;i<len;i++)

	{

		if(A[i]>=sum)

			continue;

		if(B[A[i]]==false)

			B[sum-A[i]]=true;

		else

		{

			*a=A[i];

			*b=sum-A[i];

			free(B);//释放空间

			B=NULL;

			return true;

		}

	}

	free(B);//释放空间

	B=NULL;

	return false;

}

int main()

{

	int n,k;

	static int A[1000000];

	while(scanf("%d %d",&n,&k)!=EOF)

	{

		int i;

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

		{

			scanf("%d ",A+i);

		}

		int a,b;

		bool isFind=FindNumSum(A,n,k,&a,&b);

		if(isFind)

			printf("%d %d\n",a,b);

		else

			printf("-1 -1\n");

	}

	return 0;

}

执行结果：