一个无序数组中两个数之和等于给定的值sum

大家好，欢迎来到IT知识分享网。

【问题描述】

给定一个数组，求两个数之和=给定值sum的所有组合个数。

【变形】两个数之和=sum的任意一组数

【方法一】穷举法

从数组中任意找两个数，看其和是否=sum。时间复杂度O(N^2)

【方法二】先排序，然后定义两个指针，一个i=0指向数组头，一个j=len-1指向数组的尾，看其和是否==sum；若==，则查找成功返回；若>sum，则尾指针j–；若<sum，则头指针i++。

时间复杂度：快排O(NlogN)，查找O(N)；所以总的时间复杂度为：O(NlogN)

代码：

int getSumNum(int *arr,int Sum)， //arr为数组，Sum为和 { int i,j; for(i = 0, j = n-1; i < j ; ) { if(arr[i] + arr[j] == Sum) return ( i , j ); else if(arr[i] + arr[j] < Sum) i++; else j--; } return ( -1 , -1 ); }

【方法三】hash表

给定一个数，根据hash表查找另一个数只需要O(1)的时间。但需要空间换时间，空间复杂度为O(n)；

可以用hashMap实现，hashMap<a[i], 次数>。

遍历一遍数组，若次数没有存在hashMap中，则将其加入，次数为1；再遍历一遍数组，对每个值a[i]，判断sum-a[i]是否在hashmap中【即对应的value是否==1】；若存在，则查找成功；否则继续遍历下一个。直到遍历完整个数组。

 int getSum(int *a, int len, int sum) { hash_map<int, int> map; //先遍历一遍数组，将每个数存在hashmap中，对应的value=1；表示存在次数 for(int i=0; i<len; i++) map[a[i]] = 1; //再遍历一遍数组，查看sum-i的是否在hashmap中，在则表示查找成功，不在则表示查找失败 //【若记录次数的话，每个数仅可用一次，则最后的cunt/2即为所求值】 flag=false;

 for(int i=0; i<len; i++) { if(map[a[sum-i]] == 1) { cunt++; flag=true;//表示查找到了 } } if(flag==false) return -1; else return cunt/2; }

【另一思路】

若题目中限定了数组中的元素为非负整数，因此我们可以用哈希数组，开辟一个长度为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数组，思路是一样的。

/* 在无序数组A中找出和为sum的任意两个元素，保存在a和b中 */ bool FindTwoNumSum(int *A,int len,int sum,int *a,int *b) { if(A==NULL || len<2) return false; //各元素均被初始化为false的bool数组;calloc(n, sizeof(类型))；默认初始化值全为0 bool *B = (bool*)calloc(sum,sizeof(bool)); int i; for(i=0;i<len;i++) { if(A[i]>sum)//大于sum，直接跳过 break; if(B[A[i]] == false) B[sum-A[i]] = true; else { *a = A[i]; *b = sum-A[i]; return true; } } return false; }

【注意】

calloc(n, sizeof(类型))；默认初始化值全为0【布尔型时即全为false】；而malloc默认的初始值可以为任意数。这是calloc的优势，在此定义bool型时。