## 題目描述 輸入一個數組和一個數字，在數組中查找兩個數，使得它們的和正好是輸入的那個數字。 要求時間復雜度是O(N)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。 例如輸入數組1、2、4、7、11、15和數字15。由于4+11=15，因此輸出4和11。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md#分析與解法)分析與解法 咱們試著一步一步解決這個問題（注意闡述中數列有序無序的區別）： 直接窮舉，從數組中任意選取兩個數，判定它們的和是否為輸入的那個數字。此舉復雜度為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)）。 可以繼續優化做到時間O(N)么？ ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md#解法一)解法一 根據前面的分析，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)的空間存儲第二個數組。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md#解法二)解法二 當題目對時間復雜度要求比較嚴格時，我們可以考慮下用空間換時間，上述解法一即是此思想，此外，構造hash表也是典型的用空間換時間的處理辦法。 即給定一個數字，根據hash映射查找另一個數字是否也在數組中，只需用O(1)的時間，前提是經過O(N)時間的預處理，和用O(N)的空間構造hash表。 但能否做到在時間復雜度為O(N)的情況下，空間復雜度能進一步降低達到O(1)呢？ ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md#解法三)解法三 如果數組是無序的，先排序(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)。 下面，咱們先來實現此思路（這里假定數組已經是有序的），代碼可以如下編寫： ~~~ void TwoSum(int data[], unsigned int length, int sum) { //sort(s, s+n); 如果數組非有序的，那就事先排好序O(N log N) int begin = 0; int end = length - 1; //倆頭夾逼，或稱兩個指針兩端掃描法，很經典的方法，O(N) while (begin < end) { long currSum = data[begin] + data[end]; if (currSum == sum) { //題目只要求輸出滿足條件的任意一對即可 printf("%d %d\n", data[begin], data[end]); //如果需要所有滿足條件的數組對，則需要加上下面兩條語句： //begin++ //end-- break; } else{ if (currSum < sum) begin++; else end--; } } } ~~~ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md#解法總結)解法總結 不論原序列是有序還是無序，解決這類題有以下三種辦法： * 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(Nlog N)，空間O(1)），或映射或hash（時間O(N)，空間O(N)）。時間或空間，必須犧牲一個，達到平衡。 綜上，若是數組有序的情況下，優先考慮兩個指針兩端掃描法，以達到最佳的時O(N)，空O(1)效應。否則，如果要排序的話，時間復雜度最快當然是只能達到O(N log N)，空間O(1)則不在話下。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md#問題擴展)問題擴展 1. 如果在返回找到的兩個數的同時，還要求你返回這兩個數的位置列？ 2. 如果需要輸出所有滿足條件的整數對呢? 3. 如果把題目中的要你尋找的兩個數改為“多個數”，或任意個數列? ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md#舉一反三)舉一反三 1、在二元樹中找出和為某一值的所有路徑 輸入一個整數和一棵二元樹，從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑，然后打印出和與輸入整數相等的所有路徑。 例如輸入整數22和如下二元樹 ~~~ 10 ~~~ / \ 5 12 / \ 4 7 則打印出兩條路徑：10, 12和10, 5, 7。 其中，二元樹節點的數據結構定義為： ~~~ struct BinaryTreeNode // a node in the binary tree { int m_nValue; // value of node BinaryTreeNode *m_pLeft; // left child of node BinaryTreeNode *m_pRight; // right child of node }; ~~~ 2、有一個數組a，設有一個值n。在數組中找到兩個元素a[i]和a[j]，使得a[i]+a[j]等于n，求出所有滿足以上條件的i和j。 3、3-sum問題 給定一個整數數組，判斷能否從中找出3個數a、b、c，使得他們的和為0，如果能，請找出所有滿足和為0個3個數對。 4、4-sum問題 給定一個整數數組，判斷能否從中找出4個數a、b、c、d，使得他們的和為0，如果能，請找出所有滿足和為0個4個數對。