和为定值的两个数

题目链接：
　　　http://ac.jobdu.com/problem.php?pid=1352

题目描述：: 输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输入：: 每个测试案例包括两行：

第一行包含一个整数n和k，n表示数组中的元素个数，k表示两数之和。其中1 <= n <= 10^6，k为int

第二行包含n个整数，每个数组均为int类型。

输出：: 对应每个测试案例，输出两个数，小的先输出。如果找不到，则输出“-1 -1”

样例输入：

6 15
1 2 4 7 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<A1+Ak<=A2+Ak<=,...<=Ak-1+Ak，也就是说，Ak与数列中其它任何数的和都不可能等于sum，因此抛弃Ak这个数，对结果没有影响。A1+Ak如果小于sum的话，同理抛弃A1这个数对结果没有影响。

该方法对任意的整数数组都适合，另外，要输出乘积最小的一组，没必要将所有的结果保存起来，我们由下面我们高中时非常熟悉的数学公式可以证明最左边和最右边的两个符合要求的数的乘积最小。

当a+b = c时，ab<=（a+b）的平方/4，当且仅当a==b时，ab取得最大值，二者相差越远，乘积越小。

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4  
 5 bool FindTwoNumADdeterminedSum(int* A, int n, int k);
 6  
 7 int main()
 8 {
 9     int n,k;  
10     int A[1000000];  
11     while(scanf("%d%d", &n,&k) != EOF)  
12     {  
13         int i;  
14         for(i=0;i<n;i++)  
15             scanf("%d",&A[i]);
16         FindTwoNumADdeterminedSum(A, n, k);
17     }
18     return 0;
19 }
20  
21 bool FindTwoNumADdeterminedSum(int* A, int n, int k)
22 {
23     if (A == NULL || n < 2)
24     {
25                 printf("-1 -1
");
26         return false;
27     }
28     int i = 0, j = n - 1;
29     while (i < j)
30     {
31         if (A[i] + A[j] == k)
32         {
33             printf("%d %d
",A[i], A[j]); 
34             return true;
35         }
36         else if(A[i] + A[j] < k)
37         {
38             ++i;
39         }
40         else
41         {
42             --j;
43         }
44     }
45     printf("-1 -1
");
46     return false;
47 }
48 /**************************************************************
49     Problem: 1352
50     User: yi_jian_tian
51     Language: C++
52     Result: Accepted
53     Time:1460 ms
54     Memory:5356 kb
55 ****************************************************************/

　　拓展一下，假设数组是乱序的，而且规定数组中的元素全部为非负整数，同样给定一个数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数组，思路是一样的。

　　完整代码如下：

 1 /****************************************************************************************************
 2 题目：输入一个无序的非负整数数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
 3 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
 4 例如输入数组1、7、4、11、6、15和数字15。由于4+11=15，因此输出4和11。
 5 *****************************************************************************************************/
 6 #include<stdio.h>
 7 #include<stdlib.h>
 8 
 9 /*
10 在无序数组A中找出和为sum的任意两个元素，保存在a和b中
11 */
12 bool FindTwoNumSum(int *A,int len,int sum,int *a,int *b)
13 {
14     if(A==NULL || len<2)
15         return false;
16     //各元素均被初始化为false的bool数组
17     bool *B = (bool*)calloc(sum,sizeof(bool));
18     if(B == NULL)
19         exit(EXIT_FAILURE);
20     int i;
21     for(i=0;i<len;i++)
22     {
23         if(A[i]>sum)
24             continue;
25         if(B[A[i]] == false)
26             B[sum-A[i]] = true;
27         else
28         {
29             *a = A[i];
30             *b = sum-A[i];
31             free(B);
32             B = NULL;
33             return true;
34         }
35     }
36     free(B);
37     B = NULL;
38     return false;
39 }
40 
41 int main()
42 {
43     int A[] = {19,3,9,7,12,20,17,18,1,16};
44     int len = 10;
45     int sum = 24;
46     int a,b;
47     if(FindTwoNumSum(A,len,sum,&a,&b))
48         printf("Find two nums,they are:
%d and %d
",a,b);
49     else
50         printf("Not find
");
51     return 0;
52 }