题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
咱们试着一步一步解决这个问题（注意阐述中数列有序无序的区别）：
直接穷举，从数组中任意选取两个数，判定它们的和是否为输入的那个数字。此举复杂度为O(N^2)。很显然，我们要寻找效率更高的解法。
题目相当于，对每个a[i]，查找sum-a[i]是否也在原始序列中，每一次要查找的时间都要花费为O(N)，这样下来，最终找到两个数还是需要O（N^2）的复杂度。那如何提高查找判断的速度呢？
答案是二分查找，可以将O(N)的查找时间提高到O(log N)，这样对于N个a[i]，都要花logN的时间去查找相对应的sum-a[i]是否在原始序列中，总的时间复杂度已降为O(N log N)，且空间复杂度为O(1)。 （如果有序，直接二分O(N log N)，如果无序，先排序后二分，复杂度同样为O（N log N + N log N）=O(N log N)，空间总为O(1)）。
有没有更好的办法呢？咱们可以依据上述思路2的思想，a[i]在序列中，如果a[i]+a[k]=sum的话，那么sum-a[i]（a[k])也必然在序列中。 举个例子，如下： 原始序列： 1、 2、 4、 7、11、15 用输入数字15减一下各个数，得到对应的序列为： 14、13、11、8、4、 0
第一个数组以一指针i 从数组最左端开始向右扫描，第二个数组以一指针j 从数组最右端开始向左扫描，如果下面出现了和上面一样的数，即a[*i]=a[*j]，就找出这俩个数来了。 如上，i，j最终在第一个，和第二个序列中找到了相同的数4和11，所以符合条件的两个数，即为4+11=15。 怎么样，两端同时查找，时间复杂度瞬间缩短到了O(N)，但却同时需要O(N)的空间存储第二个数组（@飞羽：要达到O(N)的复杂度，第一个数组以一指针i 从数组最左端开始向右扫描，第二个数组以一指针j 从数组最右端开始向左扫描，首先初始i指向元素1，j指向元素0，谁指的元素小，谁先移动，由于1(i)> 0(j)，所以i不动，j向左移动。然后j移动到元素4发现大于元素1，故而停止移动j，开始移动i，直到i指向4，这时,i指向的元素与j指向的元素相，故而判断4是满足条件的第一个数；然后同时移动i,j再进行判断，直到它们到达边界）。
当然，你还可以构造hash表，正如编程之美上的所述，给定一个数字，根据hash映射查找另一个数字是否也在数组中，只需用O(1)的时间，这样的话，总体的算法通上述思路3 一样，也能降到O(N)，但有个缺陷，就是构造hash额外增加了O(N)的空间，此点同上述思路 3。不过，空间换时间，仍不失为在时间要求较严格的情况下的一种好办法。
如果数组是无序的，先排序(N log N)，然后用两个指针i，j，各自指向数组的首尾两端，令i=0，j=n-1，然后i++，j--，逐次判断a[i]+a[j]?=sum，如果某一刻a[i]+a[j] > sum，则要想办法让sum的值减小，所以此刻i不动，j--，如果某一刻a[i]+a[j] < sum，则要想办法让sum的值增大，所以此刻i++，j不动。所以，数组无序的时候，时间复杂度最终为O(N log N + N）=O(N log N)，若原数组是有序的，则不需要事先的排序，直接O(N)搞定，且空间复杂度还是O(1)，此思路是相对于上述所有思路的一种改进。（如果有序，直接两个指针两端扫描，时间O(N)，如果无序，先排序后两端扫描，时间O(N log N + N)=O(N log N)，空间始终都为O(1)）。（与上述解法二相比，排序后的时间开销由之前的二分的n*logn降到了扫描的O(N)）。
下面，咱们先来实现思路5（这里假定数组已经是有序的），代码可以如下编写（两段代码实现）：
//代码一
//O（N）
Pair findSum(int *s, int n, int x)
{
//sort(s, s+n); 如果数组非有序的，那就事先排好序O(N log N)
int *begin = s;
int *end = s+n-1;
while(begin < end) //俩头夹逼，或称两个指针两端扫描法，很经典的方法，O(N)
{
if(*begin + *end > x)
{
--end;
}
else if(*begin + *end < x)
{
++begin;
}
else
{
return Pair(*begin, *end);
}
}
return Pair(-1, -1);
}
//或者如下编写，
//代码二
//copyright@ zhedahht && yansha
//July、updated，2011.05.14。
bool find_num(int data[], unsigned int length, int sum, int& first_num, int& second_num)
{
if(length < 1)
return true;
int begin = 0;
int end = length - 1;
while(end > begin)
{
long current_sum = data[begin] + data[end];
if(current_sum == sum)
{
first_num = data[begin];
second_num = data[end];
return true;
}
else if(current_sum > sum)
end--;
else
begin++;
}
return false;
}不论原序列是有序还是无序，解决这类题有以下三种办法：1、二分（若无序，先排序后二分），时间复杂度总为O(N log N)，空间复杂度为O（1）；2、扫描一遍X-S[i] 映射到一个数组或构造hash表，时间复杂度为O(N)，空间复杂度为O(N)；3、两个指针两端扫描（若无序，先排序后扫描），时间复杂度最后为：有序O(N)，无序O(N log N + N)=O(N log N)，空间复杂度都为O(1)。
所以，要想达到时间O(N)，空间O(1)的目标，除非原数组是有序的（指针扫描法），不然，当数组无序的话，就只能先排序，后指针扫描法或二分（时间 O(N log N)，空间O(1)），或映射或hash（时间O(N)，空间O(N)）。时间或空间，必须牺牲一个，自个权衡吧。
综上，若是数组有序的情况下，优先考虑两个指针两端扫描法，以达到最佳的时（O(N)），空（O(1)）效应。否则，如果要排序的话，时间复杂度最快当然是只能达到O(N log N)，空间O(1)则是不在话下。
- 如果在返回找到的两个数的同时，还要求你返回这两个数的位置列?
- 如果把题目中的要你寻找的两个数改为“多个数”，或任意个数列?（请看下面第二节）
- 二分查找时：
left <= right，right = middle - 1;left < right，right = middle;
//算法所操作的区间,是左闭右开区间,还是左闭右闭区间,这个区间,需要在循环初始化,
//循环体是否终止的判断中,以及每次修改left,right区间值这三个地方保持一致,否则就可能出错.
//二分查找实现一
int search(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right)
{
middle = left + (right - left) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
//二分查找实现二
int search(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n;
while (left < right)
{
middle = left + (right - left) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}