- 首页 > it技术 > >
输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。 时间复杂度O(N) 空间复杂度O(N)
/*
*copyright@nciaebupt 转载请注明出处
*题目：输入一个数组和一个数字，在数组中查找两个数，
*使得它们的和正好是输入的那个数字。
*如果有多对数字的和等于输入的数字，输出任意一对即可。
*例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
*数组无序的情况，使用hash的方法来加快查找速度
*时间复杂度O(N) 空间复杂度O(N)
*/
#include
#define HASHLEN 100struct HashNode
{
int num;
HashNode *next;
};
int hashFunction(int key)
{
int value = https://www.it610.com/article/0;
double SEED = 0.618;
//Knuth建议选取0.6180339887
int m = 31;
double tmp =key * SEED;
value = int(m * (tmp - int(tmp)));
return value;
}int searchNum(HashNode * hashtable,int *array,int len,int sum,int &num1,int &num2)
{
for(int i = 0;
i < len;
++i)
{int pos = hashFunction(array[i]);
HashNode * p = hashtable[pos].next;
while(p != NULL)
{
if(p->num == array[i])
{
num1 = array[i];
num2 = sum - array[i];
return 1;
}
p = p->next;
}
}
return 0;
}int main(int args,char ** argv)
{
int array[] = {1,2,15,7,11,4};
int sum = 15;
HashNode * hashtable = new HashNode[HASHLEN];
for(int i =0 ;
i < HASHLEN;
++i)
{
hashtable[i].next = NULL;
}
for(int i = 0;
i < sizeof(array)/sizeof(int);
++i)
{
int pos = hashFunction(sum - array[i]);
HashNode * p = new HashNode();
p->num = sum - array[i];
p->next = hashtable[pos].next;
hashtable[pos].next = p;
}
int num1;
int num2;
int flag = searchNum(hashtable,array,sizeof(array)/sizeof(int),sum,num1,num2);
printf("%d%d%d\n",flag,num1,num2);
getchar();
return 0;
}
推荐阅读
