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

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

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

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

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

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

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

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

　　參考代碼：    

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

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

　　}

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識點總結(jié)匯總

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

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