问题来源：《编程之美》2.12 快速寻找满足条件的两个数
能否快速找出一个数组中的两个数，让这两个数之和等于一个给定的数字，为了简化起见，我们假设这个数组中肯定存在至少一组符合要求的解。
解题思路：
可以先将数组升序排序，然后设定变量i = 0，j = size - 1，看array[i] + array[j] 是否等于sum, 如果相等，则结束。如果小于sum，则 i = i + 1; 如果大于sum，则 j = j - 1。这样只需要在排好序的数组上遍历一次就可以得到最后的结果，时间复杂度为O(n), 加上排序的时间复杂度，总的复杂度为O(n*log2n)。
程序描述如下：
#include <stdlib.h>
#include <stdio.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//快速排序, 将第一个元素作为参考元素
void quickSort(int array[], int left, int right)
{
if(left < right) {
int i = left;
int j = right + 1;
while(1) {
do
++i;
while(array[i] < array[left] && i < right); //从左向右寻找比array[left]大或相等的元素位置
do
--j;
while(array[j] >= array[left] && j > left); //从右向左寻找比arrya[left]小的元素位置
if(i < j) //如果还没有遍历完整个数组，则交换元素使较小元素靠前，较大元素靠后
swap(&array[i], &array[j]);
else //此时整个数组的元素已全部遍历，array[j]中存储的是从右向左遍数组遇到的第一个小于array[left]的元素
break;
}
swap(&array[left], &array[j]); //交换array[left]和array[j], 这样array[j]就处在了整个数组排序后的最终位置上
//array[j]将数组分为两部分，递归调用排序其左边元素及右边元素
quickSort(array, left, j - 1);
quickSort(array, j + 1, right);
}
}
int isExistSum(int array[], int size, int sum, int *index1, int *index2)
{
int i = 0;
int j = size -1;
while(i < j) {
if(array[i] + array[j] > sum)
--j;
else if(array[i] + array[j] < sum)
++i;
else {
*index1 = i;
*index2 = j;
return 1;
}
}
*index1 = -1;
*index2 = -1;
return 0;
}
int main()
{
int a[] = {-999, 100, 50, 15, 100, 12, -999, -1000, -2000, -15555, -9999, 100, 100, 0};
quickSort(a, 0, sizeof(a)/sizeof(int)-1);
for(int i = 0; i < sizeof(a)/sizeof(int); ++i)
printf("%d ", a[i]);
printf("\n");
int index1, index2;
isExistSum(a, sizeof(a)/sizeof(int), 100, &index1, &index2);
printf("index1 = %d, index2 = %d\n", index1, index2);
}