来源：

求已知集合中某两个或三个元素之和等于确定值问题 收藏
问题描述：

1、给定一个数组，该数组包含N个元素。我们想要确定是否存在两个数它们的和等于给定的数K。例如，如果输入是8，4，1，6而K是10，则答案为yes（4和6）。一个数可以被使用两次。
给出求解该问题的O（NlogN）算法。

2、1、给定一个数组，该数组包含N个元素。我们想要确定是否存在三个数它们的和等于给定的数K。例如，如果输入是8，4，1，6而K是13，则答案为yes（8和4和1）。一个数可以被使用两次或三次。
给出求解该问题的O（N2）算法。

解题思路：

1，首先用快速排序或并归排序将已知集合排序（nlogn），然后用类似于快速排序的方法操作，代码如下：

//L是已经排序好的数组

bool f( int *L, int len, int sum ){
int i=0, j=len-1;
while( i<j ){ if( L[i]+L[j]==sum )
return true;
else
if( L[i]+L[j]>sum )
--j;
else
++i;
}
return false;
}
2，先将数组按递增进行快速排序，快速排序的复杂度是O(nlogn)的。
还是用问题1的方法，我们从问题1的解决方法中可以看到：
如果数组是有序的，那么确定是否存在两个数它们的和等于给定的数sum的算法的时间复杂度是O(n)的（n为数组长度）。

现在，我们要找确定是否存在L[i]+L[j]+L[k]=sum。  （1）
不妨令L[i] <=L[j] <=L[k]
我们现在将（1）式变为: L[i]+L[j]=sum-L[k]
令SUM=sum-L[k]。
现在，容易看到SUM的值只可能有n个，而对每一个SUM，我们确定是否存在两个数它们的和等于给定的数SUM的时间复杂度是O(n)的，于是，总的时间复杂度是：
O(nlogn+n^2)=O(n^2)。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

方法三，通过借助辅助数组的方法，让b[i] = sum - a[i]; 然后通过找到数组a

和数组b的交集，其相对位置上的数就是我们要找的数值对。这里的代码用了二分

查找，这个二分查找的序列是从大到小排列的，所以自己实现了一个二分查找算法。

另外可以通过题目39中求差集的办法，不过要将数组b排序。

1. void FindSumN_3(int*a, int n, int sum)  
2. {  
3.     int * b = (int*)malloc(n*sizeof(int));  
4.     int i,j;  
5.     for(i = 0; i < n; i++)  
6.     {  
7.         b[i] = sum - a[i];  
8.     }  
9.     for( i = 0; i < n; i++)  
10.     {  
11.         if(j = BinarySearch(b,n,a[i]))  
12.         {  
13.             printf("a[%d] + a[%d] = %d\n",i,j,sum);  
14.         }  
15.     }  
16.     free(b);  
17. } 
    
18. 来源：