程序員面試題精選100題(10)-排序數組中和為給定值的兩個數字[算法]

時間:2019-09-22 編輯:范文亭

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

例如輸入數組12471115和數字15。由于4+11=15,因此輸出411

分析:如果我們不考慮時間復雜度,最簡單想法的莫過去先在數組中固定一個數字,再依次判斷數組中剩下的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

本文已影響
相關文章
大亨pk10计划苹果版