微軟等數據結構與算法面試100題 第十四題

第十四題

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

分析：
這道題目比較簡單，見代碼。說明：代碼是給出的所有的組合。
代碼：
[cpp] 
#include<iostream> 
 
using namespace std; 
 
bool findSum(int *a, const int length, int sum) 
{ 
    bool yesno = false; 
    int startIndex = 0; 
    int endIndex = length-1; 
    if(endIndex < 1) return false; 
     
    int tempSum; 
    while(startIndex<endIndex) 
    { 
        tempSum = a[startIndex] + a[endIndex]; 
        if(tempSum>sum) 
        { 
            endIndex--; 
        } 
        else if(tempSum<sum) 
        { 
            startIndex++; 
        } 
        else 
        { 
            cout<<a[startIndex]<<" "<<a[endIndex]<<endl; 
            yesno = true; 
            startIndex++; 
        } 
             
    } 
 
    return yesno; 
 
} 
int main() 
{ 
    int a[10] = {1,2,3,4,5,6,7,8,9,10}; 
 
    cout<<findSum(a,10,10); 
    return 0; 
} 

輸出結果為
1 9
2 8
3 7
4 6