求数组中和为给定值的任意两个数

题目：

输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

思路：

最直接的做法是暴力法，两个for循环，时间复杂度为O（n*n），但是这样没有充分利用升序数组这一前提。我们假设数组为A，长度为len，给定的和为sum，最好的方法是先用数组的第一个数A[low]和最后一个数A[high]相加，看是否等于sum，如果等于sum，则找到了一组数，返回true，如果大于sum，则将较大的数向前移动一位，即high--，此时变成了第一个和倒数第二个数相加，如果小于sum，则将较小的数向后移动一位，即low++，此时变成了第二个和最后一个数相加，依此类推，如果low==high时还未找到和为sum的一组数，则返回false。该算法的时间复杂度为O（n），空间复杂度为O（1）。

针对该方法需要给出一些证明，证明如下：

对于一个升序数列A1,A2,...Ak k>=3，如果A1+Ak大于sum，那么考察k-1个数对和A1+Ak,A2+Ak,...Ak-1+Ak有sum

该方法对任意的整数数组都适合。

完整代码

/****************************************************************************************************
题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
*****************************************************************************************************/
#include
  
   

/*
在升序数组A中找出和为sum的任意两个元素，保存在a和b中
*/
bool FindTwoNumSum(int *A,int len,int sum,int *a,int *b)
{
	if(A==NULL || len<2)
		return false;
	int low = 0;
	int high = len-1;
	while(low
   
     测试结果 
     我们现在来拓展一下，假设数组是乱序的，而且规定数组中的元素全部为非负整数，同样给定一个数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(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、7、4、11、6、15和数字15。由于4+11=15，因此输出4和11。
*****************************************************************************************************/
#include
     
      
#include
      
        /* 在无序数组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数组 bool *B = (bool*)calloc(sum,sizeof(bool)); if(B == NULL) exit(EXIT_FAILURE); int i; for(i=0;i
       
        sum) break; 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 A[] = {19,3,9,7,12,20,17,18,1,16}; int len = 10; int sum = 24; int a,b; if(FindTwoNumSum(A,len,sum,&a,&b)) printf(Find two nums,they are: %d and %d ,a,b); else printf(Not find ); return 0; } 
       
      
     
 测试结果：