前奏
希望此編程藝術系列能給各位帶來的是一種方法，一種創造力，一種舉一反三的能力。本章依然同第四章一樣，選取比較簡單的面試題，恭祝各位旅途愉快。同樣，有任何問題，歡迎不吝指正。謝謝。
第一節、尋找滿足條件的兩個數
第14題（數組）：
題目：輸入一個數組和一個數字，在數組中查找兩個數，使得它們的和正好是輸入的那個數字。
要求時間復雜度是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（logN），這樣對於N個a[i]，都要花logN的時間去查找相對應的sum-a[i]是否在原始序列中，總的時間復雜度已降為O（N*logN），且空間復雜度為O（1）。（如果有序，直接二分O（N*logN），如果無序，先排序後二分，復雜度同樣為O（N*logN+N*logN）=O（N*logN），空間總為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*logn），然後用兩個指針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*logn+n）=O（n*logn），若原數組是有序的，則不需要事先的排序，直接O（n）搞定，且空間復雜度還是O（1），此思路是相對於上述所有思路的一種改進。（如果有序，直接兩個指針兩端掃描，時間O（N），如果無序，先排序後兩端掃描，時間O（N*logN+N）=O（N*logN），空間始終都為O（1））。（與上述思路2相比，排序後的時間開銷由之前的二分的n*logn降到了掃描的O（N））。
總結：
不論原序列是有序還是無序，解決這類題有以下三種辦法：1、二分（若無序，先排序後二分），時間復雜度總為O（n*logn），空間復雜度為O（1）；2、掃描一遍X-S[i] 映射到一個數組或構造hash表，時間復雜度為O（n），空間復雜度為O（n）；3、兩個指針兩端掃描（若無序，先排序後掃描），時間復雜度最後為：有序O（n），無序O（n*logn+n）=O（n*logn），空間復雜度都為O（1）。
所以，要想達到時間O（N），空間O（1）的目標，除非原數組是有序的（指針掃描法），不然，當數組無序的話，就只能先排序，後指針掃描法或二分（時間n*logn，空間O（1）），或映射或hash（時間O（n），空間O（n））。時間或空間，必須犧牲一個，自個權衡吧。
綜上，若是數組有序的情況下，優先考慮兩個指針兩端掃描法，以達到最佳的時（O（N）），空（O（1））效應。否則，如果要排序的話，時間復雜度最快當然是只能達到N*logN，空間O（1）則是不在話下。
代碼：
ok，在進入第二節之前，咱們先來實現思路5（這裡假定數組已經是有序的），代碼可以如下編寫（兩段代碼實現）：
view plaincopy to clipboardprint?
//代碼一
//O（N）
Pair findSum(int *s,int n,int x)
{
//sort(s,s+n); 如果數組非有序的，那就事先排好序O（N*logN）
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、如果在返回找到的兩個數的同時，還要求你返回這兩個數的位置列?
2、如果把題目中的要你尋找的兩個數改為“多個數”，或任意個數列?（請看下面第二節）
3、二分查找時： left <= right，right = middle - 1;left < right，right = middle;
//算法所操作的區間,
