首页 > 代码库 > 【剑指offer学习】求和为定值的两个数(拓展)

【剑指offer学习】求和为定值的两个数(拓展)

接着上面一篇文章: 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;
}


执行结果:








【剑指offer学习】求和为定值的两个数(拓展)