查看匯總：2015軟件水平考試程序員精選題匯總

　　-在排序數組中查找和為給定值的兩個數字

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

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

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

　　我們假設現在隨便在數組中找到兩個數。如果它們的和等于輸入的數字，那太好了，我們找到了要找的兩個數字;如果小于輸入的數字呢?我們希望兩個數字的和再大一點。由于數組已經排好序了，我們是不是可以把較小的數字的往后面移動一個數字?因為排在后面的數字要大一些，那么兩個數字的和也要大一些，就有可能等于輸入的數字了;同樣，當兩個數字的和大于輸入的數字的時候，我們把較大的數字往前移動，因為排在數組前面的數字要小一些，它們的和就有可能等于輸入的數字了。

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

　　問題是這樣的思路是不是正確的呢?這需要嚴格的數學證明。感興趣的讀者可以自行證明一下。

　　參考代碼：    

　　///////////////////////////////////////////////////////////////////////

　　// 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 array

　　unsigned int length, // the length of the sorted array

　　int sum, // the sum

　　int& num1, // the first number, output

　　int& 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 them

　　if(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 number

　　else if(curSum > sum)

　　ahead --;

　　// if the sum of two numbers is less than the input

　　// increase the less number

　　else

　　behind ++;

　　}

　　return found;

　　}

　　相關推薦：

　　2015年軟考信息技術處理員考前知識點總結匯總

　　2015年軟件水平考試《程序員》提高練習題匯總

　　2015軟件水平考試《程序員》知識點總結匯總