一、问题
能否快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的数字，为了简化起见，我们假设这个数组中肯定存在至少一组符合要求的解。
问题分析：
输入：一个长度为N的数组和一个给定的数X。
输出：数组中的两个数字A和B。
约束：X = A + B，且A和B至少存在一组。
其他：题目中只说了数字，说明这些数可能为正整数、负整数、零或浮点数等，不太可能通过给定数字X并抛开数组来遍历各种A和B的组合并判断它们是否在数组中。并且题目也没有告诉我们关于数组的数据规模大小和数据特点。
二、解法
版本一：暴力破解法——遍历数组
算法：最简单的思路遍历一遍数组，对于数组中的每个值A，求解X-A，并在数组未被遍历的部分中对数组进行第二层遍历来查找是否含有值B=X-A的数，若找到则输出A和B。
时间复杂度：最好的情况是O(1)，数组中的前两个数A和B，恰好满足A+B=N；最差的情况是O(n^2)，数组中只存在末尾两个数A和B，满足A+B=N。
分析：《编程之美》也提到了这种方法（穷举法，我这里使用的名字"暴力破解法"源自《算法导论》，它们的思路是一致的），算法时间复杂度为O(n^2)，效率较低 。
算法C实现：
1.输入时把最后一个输入的值作为题目输入中的一个给定的数X，把它前面的数作为题目输入中的数组数据。
2.尽管题目约束条件讲了满足X=A+B的A和B至少存在一组，算法还是对A和B是否存在进行了检测，它利用函数返回的标志位检测是否找到这两个值。
/**
* @brief find two numbers value_a and value_b in the array
* (with limit length) with given sum to make: sum = value_a + value_b
*
* @param[in] array input array
* @param[in] length array length
* @param[in] sum sum that makes sum = value_a + value_b
* @param[out] value_a value_a in the array
* @param[out] value_b value_b in the array
*
* @return if get value_a and value_b, return 1, else return 0
*/
TYPE find_two_numbers(TYPE* array, TYPE length, TYPE sum,
TYPE* value_a, TYPE* value_b)
{
assert(array != NULL && length >= 2 && value_a != NULL && value_b != NULL);
TYPE i, j;
for (i = 0; i < length - 1; i++) {
/// set value a
*value_a = array[i];
/// find value b
*value_b = sum - array[i];
for (j = i + 1; j < length; j++) {
if (*value_b == array[j])
return 1;
}
}
return 0;
}
版本二：排序+二分查找
自己的思路：在前面问题分析中说过不太可能抛开数组只从给定的数X入手，可以从“对数组进行预处理”这个角度来思考问题。我们可以对数组从小到大进行排序，利用快速排序的时间复杂度是O(nlgn)，接下来的我们可以发现，按照版本一的思路遍历数组求解A和B时，对于遍历数组时的一个数a1，我们先找到数组中满足a1 + am >= X的最小的数am，接下来进行第二层遍历寻找b1=X-a1这个数时，我们只需要让b1从am开始进行遍历即可。如果我们采用遍历的方式来搜索am（算法复杂度O(n)），那么算法的总时间复杂度与版本一是一致的，只是这里利用了比较语句而不是判断语句。但若采用更高效的搜索方法（如二分搜索等）来搜索am，那么算法的总时间复杂度肯定会比版本一的总时间复杂度低。
思路补充：《编程之美》中也提出了对排序数组进行二分查找（或其他高效查找方法）的方式，与我所想的思路的区别是：在寻找上面定义的b1时就采用二分搜索，而不是去先二分搜索am再遍历搜索b1，比我上面的思路更加开阔，全面利用了二分查找的快速性。
（《编程之美》原话：学过编程的人都知道，提高查找效率通常可以先将要查找的数组排序，然后用二分查找等方法进行查找，就可以将原来O(N)的查找时间缩短找O(lgN)。）
时间复杂度：快速排序算法时间复杂度O(nlgn)；遍历数组中的每个数A的时间复杂度为O(n)，而遍历过程中查找对应的数B（满足X = A + B）时使用二分查找算法，二分查找算法时间复杂度为O(lgn)，所以查找A和B总的时间复杂度为O(nlgn)。排序算法和查找算法按序进行，因此总的时间复杂度也是O(nlgn)。
算法C实现：
1.对数组进行排序采用快速排序算法。
2.对数组进行查找采用二分查找算法。
/**
* @brief select the last element as a pivoit.
* Reorder the array so that all elements with values less than the pivot
* come before the pivot, while all elements with values greater than the pivot
* come after it (equal values can go either way). After this partitioning, the
* pivot is in its final position.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*
* @return the position of the pivot(index from the array)
*/
TYPE partition(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// pick last element of the array as the pivot
TYPE pivot = array[index_end];
/// index of the elments that not greater than pivot
TYPE i = index_begin - 1;
TYPE j, temp;
/// check array's elment one by one
for (j = index_begin; j < index_end; j++) {
if (array[j] <= pivot) {
/// save the elements not greater than pivot to left index of i.
i++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
/// set the pivot to the right position
array[index_end] = array[++i];
array[i] = pivot;
/// return the position of the pivot
return i;
}
/**
* @brief quick sort method for input array from index_begin to index_end.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*/
void quick_sort(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// sort only under the index_begin < index_end condition
if ( index_begin < index_end) {
/// exchange elements to the pivot position by partition function
TYPE index_pivot = partition(array, index_begin, index_end);
/// sort the array before the pivot position
quick_sort(array, index_begin, index_pivot - 1);
/// sort the array after the pivot position
quick_sort(array, index_pivot + 1, index_end);
}
}
/**
* @brief search the value in the array of the index by binary search method.
*
* @param[in] array input array
* @param[in] count array length
* @param[in] value search value
*
* @warning array index begin from 0
*
* @return index if success, else return -1
*/
TYPE binary_search(TYPE* array, TYPE count, TYPE value)
{
assert(array != NULL && count >= 0);
TYPE middle;
TYPE index_begin = 0;
TYPE index_end = count - 1;
while (index_begin <= index_end) {
middle = index_begin + ((unsigned)(index_end - index_begin) >> 1);
if (array[middle] == value)
return middle;
else if (array[middle] < value)
index_begin = middle + 1;
else
index_end = middle - 1;
}
return -1;
}
/**
* @brief find two numbers value_a and value_b in the array
* (with limit length) with given sum to make: sum = value_a + value_b
*
* @param[in] array input array
* @param[in] length array length
* @param[in] sum sum that makes sum = value_a + value_b
* @param[out] value_a value_a in the array
* @param[out] value_b value_b in the array
*
* @return if get value_a and value_b, return 1, else return 0
*/
TYPE find_two_numbers(TYPE* array, TYPE length, TYPE sum,
TYPE* value_a, TYPE* value_b)
{
assert(array != NULL && length >= 2 && value_a != NULL && value_b != NULL);
/// sort array by quick sort method
quick_sort(array, 0, length - 1);
/// iterative for all value in array
TYPE i;
for (i = 0; i < length - 1; i++) {
/// set value a
*value_a = array[i];
/// find value b
*value_b = sum - array[i];
/// search value by binary search method
if (binary_search(array, length, *value_b) != -1)
return 1;
}
return 0;
}
版本三：哈希查找
思路（引自《编程之美》）：查找使用hash表。因为给定一个数字，根据hash映射查找另一个数字是否在数组中，只需用O(1)时间。这样的话，总体的算法复杂度可以降低到O(N)，但这种方法需要额外增加O(N)的hash表存储空间。在有的情况下，用空间换时间也并不失为一个好方法。
时间复杂度：O(n)；空间复杂度O(n)。
分析：和其他算法相比，这个hash表算法是典型地使用空间换时间的一种查找算法。
版本四：排序+两个指针两端扫描法
思路（引自《编程之美》）：可以直接对两个数字的和进行一个有序的遍历，从而降低算法的时间复杂度。
步骤：
1.首先对数组进行排序，时间复杂度为O(nlgn)。
2.然后令i = 0，j = n-1，看arr[i] + arr[j] 是否等于Sum，如果是，则结束。如果小于Sum，则i = i + 1；如果大于Sum，则 j = j – 1。这样只需要在排好序的数组上遍历一次，就可以得到最后的结果，时间复杂度为O(n)。
时间复杂度：O(nlgn + n) = O(nlgn)；空间复杂度O(1)。
分析：算法关键的一步是利用排序后指向数组两端的两个指针，通过判断Sum的大小来移动指针，在查找过程每次只移动其中一个指针，从而实现了O(n)的效率来查找满足条件的两个数（数组中利用两个下标进行遍历）。如果原来输入数组就是有序的，那么使用这个算法解决本问题的效率是最佳的。
算法C实现：
/**
* @brief select the last element as a pivoit.
* Reorder the array so that all elements with values less than the pivot
* come before the pivot, while all elements with values greater than the pivot
* come after it (equal values can go either way). After this partitioning, the
* pivot is in its final position.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*
* @return the position of the pivot(index from the array)
*/
TYPE partition(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// pick last element of the array as the pivot
TYPE pivot = array[index_end];
/// index of the elments that not greater than pivot
TYPE i = index_begin - 1;
TYPE j, temp;
/// check array's elment one by one
for (j = index_begin; j < index_end; j++) {
if (array[j] <= pivot) {
/// save the elements not greater than pivot to left index of i.
i++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
/// set the pivot to the right position
array[index_end] = array[++i];
array[i] = pivot;
/// return the position of the pivot
return i;
}
/**
* @brief quick sort method for input array from index_begin to index_end.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*/
void quick_sort(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// sort only under the index_begin < index_end condition
if ( index_begin < index_end) {
/// exchange elements to the pivot position by partition function
TYPE index_pivot = partition(array, index_begin, index_end);
/// sort the array before the pivot position
quick_sort(array, index_begin, index_pivot - 1);
/// sort the array after the pivot position
quick_sort(array, index_pivot + 1, index_end);
}
}
/**
* @brief find two numbers value_a and value_b in the array
* (with limit length) with given sum to make: sum = value_a + value_b
*
* @param[in] array input array
* @param[in] length array length
* @param[in] sum sum that makes sum = value_a + value_b
* @param[out] value_a value_a in the array
* @param[out] value_b value_b in the array
*
* @return if get value_a and value_b, return 1, else return 0
*/
TYPE find_two_numbers(TYPE* array, TYPE length, TYPE sum,
TYPE* value_a, TYPE* value_b)
{
assert(array != NULL && length >= 2 && value_a != NULL && value_b != NULL);
/// sort array by quick sort method
quick_sort(array, 0, length - 1);
/// search by two pointers at the begining and end of the array
TYPE i = 0, j = length - 1, sum_temp;
while (i < j) {
sum_temp = array[i] + array[j];
if (sum_temp < sum) {
i++;
} else if (sum_temp > sum) {
j--;
} else {
*value_a = array[i];
*value_b = array[j];
return 1;
}
}
return 0;
}
三、拓展
1.如果把这个问题中的“两个数字”改为“三个数字”或“任意个数字”时，如何求解？
思路：
首先分析“两个数字”问题时解法：如果数组本身是有序的，那么不必对数组进行排序，此时采用版本一暴力破解法时时间复杂度为O(n^2)，采用版本五两个指针两端扫描法时时间复杂度为O(n)，两个方法相比后一个方法时间复杂度降了一个数量级n。
进一步分析可以得到“三个数字”问题时解法：如果数组本身是有序的，那么不必对数组进行排序，此时采用暴力破解法时时间复杂度为O(n^3)，采用两个指针两端扫描法，此时遍历时（设三个待求解的数分别为A，B，C）固定一个数A，对另外两个数B和C采用两个指针两端扫描，时间复杂度为O(n^2)，两个方法相比后一个方法时间复杂度也是降了一个数量级n。
对于“任意个数字”问题时解法：根据上面的思路，可以逐步增加数字的个数m并结合两个指针两端扫描法综合求解，数字个数为1时时间复杂度O(1)，数字个数为2时时间复杂度O(n^2)，，数字个数为3时时间复杂度O(n^3)，当数字个数m大于数组长度(N)一半时，我们可以先求整个数组的和S（注意溢出），遍历时改为遍历N-m个数并结合两个指针两端扫描法对(N-m)个数求和，与(S
- X) 判断，相等时得解，但此时解时另外m个数（数组中剔除遍历时用到的N-m个数）。这样，“任意个数字”时算法的时间复杂度最高情况下为O(n^(k))，k = n / 2。可以预计到时间复杂度会比直接采用暴力破解法降低一个数量级n。
优化：
1.“三个数字“或“任意个数字”采用两端指针扫描法时可以采用递归实现，递归接口包含了数组个数这个参数，简化代码。（递归实现想法参考自：http://blog.csdn.net/hackbuteer1/article/details/6699642）
注意：
1.数组只用排序一次。
2.“三个数字”问题在使用递归实现时，数组排好序后，从做到右遍历A，对于B和C，只需在A右端的剩余数组中进行递归实现。
2.如果完全相等的一对数字对找不到，能否找出和最接近的解？
思路：找最接近的解，可转化为求使得abs(A+B - X)最小的值，通过遍历A和B时记录使前面等式达到更小时A和B的值来实现。遍历过程中，当等式值为0时，说明存在，直接输出；若等式一直不为零，则完全遍历A和B后再输出A和B的值，此时A和B就是最接近的解了。
算法C实现：
注意：
1.算法实现基于上面排序+两个指针两端扫描法实现。
1.函数返回1时表示找到完全相等的解value_a和value_b，函数返回0时表示找到最接近的解value_a和value_b。
/**
* @brief select the last element as a pivoit.
* Reorder the array so that all elements with values less than the pivot
* come before the pivot, while all elements with values greater than the pivot
* come after it (equal values can go either way). After this partitioning, the
* pivot is in its final position.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*
* @return the position of the pivot(index from the array)
*/
TYPE partition(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// pick last element of the array as the pivot
TYPE pivot = array[index_end];
/// index of the elments that not greater than pivot
TYPE i = index_begin - 1;
TYPE j, temp;
/// check array's elment one by one
for (j = index_begin; j < index_end; j++) {
if (array[j] <= pivot) {
/// save the elements not greater than pivot to left index of i.
i++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
/// set the pivot to the right position
array[index_end] = array[++i];
array[i] = pivot;
/// return the position of the pivot
return i;
}
/**
* @brief quick sort method for input array from index_begin to index_end.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*/
void quick_sort(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// sort only under the index_begin < index_end condition
if ( index_begin < index_end) {
/// exchange elements to the pivot position by partition function
TYPE index_pivot = partition(array, index_begin, index_end);
/// sort the array before the pivot position
quick_sort(array, index_begin, index_pivot - 1);
/// sort the array after the pivot position
quick_sort(array, index_pivot + 1, index_end);
}
}
/**
* @brief find two numbers value_a and value_b in the array
* (with limit length) with given sum to make: sum closest to value_a + value_b
*
* @param[in] array input array
* @param[in] length array length
* @param[in] sum sum that makes sum = value_a + value_b
* @param[out] value_a value_a in the array
* @param[out] value_b value_b in the array
*
* @return if get value_a and value_b, return 1, else return 0
*/
TYPE find_best_two_numbers(TYPE* array, TYPE length, TYPE sum,
TYPE* value_a, TYPE* value_b)
{
assert(array != NULL && length >= 2 && value_a != NULL && value_b != NULL);
/// sort array by quick sort method
quick_sort(array, 0, length - 1);
/// search by two pointers at the begining and end of the array
TYPE i = 0, j = length - 1, sum_diff_min = INT_MAX, sum_diff;
while (i < j) {
sum_diff = abs(array[i] + array[j] - sum);
/// record closet value_a and value_b
if (sum_diff < sum_diff_min) {
sum_diff_min = sum_diff;
*value_a = array[i];
*value_b = array[j];
}
if (sum_diff < 0) {
i++;
} else if (sum_diff > 0) {
j--;
} else {
/// get value_a and value_b with no error
return 1;
}
}
/// get value_a and value_b with error
return 0;
}
3.把上面的两个问题综合起来，就得到这样一个题目：给定一个数N，和一组数字集合S，求S中和最接近N的子集。