[置頂] 【劍指offer學習】求和為定值的兩個數
來源：程序員人生 發布時間：2014-11-04 08:42:21 閱讀次數：2004次
- 《神雕俠侶》中的‘劍冢’，收存著‘劍魔獨孤求敗’生平用過的3把劍：“楊過提起右首第1柄劍，只見劍下的石上刻有兩行小字‘凌厲剛猛，無堅不摧，弱冠前以之與河朔群雄爭鋒’；第2把是玄鐵重劍：‘重劍無鋒，大巧不工。410歲前恃之橫行天下’；第3把則是木劍，劍下的石刻道：‘410歲后，不滯于物，草木竹石都可為劍。自此精修，漸進于無劍勝有劍之境?！Ｋ惴ǖ木A也在于此，只有突破1層層境地，才能有所突破。
題目描寫：
- 輸入1個遞增排序的數組和1個數字S，在數組中查找兩個數，是的他們的和正好是S，如果有多對數字的和等于S，輸出兩個數的乘積最小的。
- 輸入：
-
每一個測試案例包括兩行：
第1行包括1個整數n和k，n表示數組中的元素個數，k表示兩數之和。其中1 <= n <= 10^6，k為int
第2行包括n個整數，每一個數組均為int類型。
- 輸出：
- 對應每一個測試案例，輸出兩個數，小的先輸出。如果找不到，則輸出“⑴ ⑴”
- 樣例輸入：
-
6 15
1 2 4 7 11 15
- 樣例輸出：
-
4 11
思路：這1道題目很簡單， 其中最直接的做法是暴力破解法，用兩個for循環，時間復雜度為O（n*n），但是這樣沒有充分利用升序數組這1條件，并且效力極低。
可以用類似于2分查找的方法來求，假定數組為A，長度為len，給定的和為sum，最好的方法是先用數組的第1個數A[low]和最后1個數A[high]相加，看是不是等于sum，如果等于sum，則找到了1組數，返回true，如果大于sum，則將較大的數向前移動1位，即high--，此時變成了第1個和倒數第2個數相加，如果小于sum，則將較小的數向后移動1位，即low++，此時變成了第2個和最后1個數相加，依此類推，如果low==high時還未找到和為sum的1組數，則返回false。該算法的時間復雜度為O（n），空間復雜度為O（1）。
實現代碼以下：
<span style="font-size:18px;">// offer01.cpp : 定義控制臺利用程序的入口點。
//
#include "stdio.h"
//在升序數組A中找出和為sum的任意兩個元素，并且保存在a和b中
bool FindNumSum(int *A,int len,int sum,int *a,int *b)
{
if(A==NULL||len<2||A[0]>sum)
return false;
int low=0;
int high=len⑴;
while(low<high)
{
if(A[low]+A[high]==sum)
{
*a=A[low];
*b=A[high];
return true;
}
else if(A[low]+A[high]<sum)
low++;
else
high--;
}
return false;
}
//main 函數
int main()
{
int n,k;
static int A[1000000];
while(scanf("%d %d",&n,&k)!=EOF)
{
int i;
for(i=0;i<n;i++)
{
scanf("%d ",A+i);
}
int a,b;
bool isFind=FindNumSum(A,n,k,&a,&b);
if(isFind)
printf("%d %d
",a,b);
else
printf("⑴ ⑴
");
}
return 0;
}
</span>
參考1些資料：
針對該方法需要給出1些證明，證明以下：
該方法對任意的整數數組都合適，另外，要輸出乘積最小的1組，沒必要將所有的結果保存起來。
當a+b = c時，ab<=（a+b）^2/4，當且僅當a==b時，ab獲得最大值，2者相差越遠，乘積越小。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
