題目：輸入一個(gè)已經(jīng)按升序排序過的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。

例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。

分析：如果我們不考慮時(shí)間復(fù)雜度，最簡(jiǎn)單想法的莫過去先在數(shù)組中固定一個(gè)數(shù)字，再依次判斷數(shù)組中剩下的n-1個(gè)數(shù)字與它的和是不是等于輸入的數(shù)字。可惜這種思路需要的時(shí)間復(fù)雜度是O(n²)。

我們假設(shè)現(xiàn)在隨便在數(shù)組中找到兩個(gè)數(shù)。如果它們的和等于輸入的數(shù)字，那太好了，我們找到了要找的兩個(gè)數(shù)字；如果小于輸入的數(shù)字呢？我們希望兩個(gè)數(shù)字的和再大一點(diǎn)。由于數(shù)組已經(jīng)排好序了，我們是不是可以把較小的數(shù)字的往后面移動(dòng)一個(gè)數(shù)字？因?yàn)榕旁诤竺娴臄?shù)字要大一些，那么兩個(gè)數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了；同樣，當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字的時(shí)候，我們把較大的數(shù)字往前移動(dòng)，因?yàn)榕旁跀?shù)組前面的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。

我們把前面的思路整理一下：最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往前移動(dòng)；當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，把較小的數(shù)字往后移動(dòng)；當(dāng)相等時(shí)，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。

問題是這樣的思路是不是正確的呢？這需要嚴(yán)格的數(shù)學(xué)證明。感興趣的讀者可以自行證明一下。

參考代碼：

/// // Find two numbers with a sum in a sorted array // Output: ture is found such two numbers, otherwise false /// bool FindTwoNumbersWithSum (int data[], // a sorted arrayunsigned int length, // the length of the sorted array int sum, // the sumint& num1, // the first number, outputint& num2 // the second number, output ) {bool found = false;if(length < 1)return found;int ahead = length - 1;int behind = 0;while(ahead > behind){long long curSum = data[ahead] + data[behind];// if the sum of two numbers is equal to the input// we have found themif(curSum == sum){num1 = data[behind];num2 = data[ahead];found = true;break;}// if the sum of two numbers is greater than the input// decrease the greater numberelse if(curSum > sum)ahead --;// if the sum of two numbers is less than the input// increase the less numberelsebehind ++;}return found; }

擴(kuò)展（1）：輸入一個(gè)數(shù)組，判斷這個(gè)數(shù)組中是不是存在三個(gè)數(shù)字i, j, k，滿足i+j+k等于0。在我的英文博客http://codercareer.blogspot.com/2011/10/no-09-numbers-with-given-sum.html里詳細(xì)討論了這個(gè)題目。

擴(kuò)展（2）：如果輸入的數(shù)組是沒有排序的，但知道里面數(shù)字的范圍，其他條件不變，如何在O(n)時(shí)間里找到這兩個(gè)數(shù)字？這個(gè)的基本思路是先用哈希表實(shí)現(xiàn)O(n)的排序（請(qǐng)參照本面試題系列的第57題），接下來的步驟都一樣了。

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動(dòng)，書中的分析講解更加詳細(xì)。歡迎關(guān)注。

?????????? 本題已被九度Online Judge系統(tǒng)收錄，歡迎讀者移步到http://ac.jobdu.com/hhtproblems.php在線測(cè)試自己的代碼。

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(10)－排序数组中和为给定值的两个数字[算法]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。