874
劍指Offer之和為S的兩個數字
- 題目描述：
- 輸入一個遞增排序的數組和一個數字S，在數組中查找兩個數，是的他們的和正好是S，如果有多對數字的和等於S，輸出兩個數的乘積最小的。
- 輸入：
-
每個測試案例包括兩行：第一行包含一個整數n和k，n表示數組中的元素個數，k表示兩數之和。其中1 <= n <= 10^6，k為int第二行包含n個整數，每個數組均為int類型。
- 輸出：
- 對應每個測試案例，輸出兩個數，小的先輸出。如果找不到，則輸出“-1 -1”
- 樣例輸入：
-
6 15 1 2 4 7 11 15
- 樣例輸出：
-
4 11
/*********************************
* 日期：2013-11-28
* 作者：SJF0115
* 題號: 題目1352：和為S的兩個數字
* 來源：https://ac.jobdu.com/problem.php?pid=1352
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
int *array;
int FindNum(int *array,int n,int m,int &num1,int &num2){
int sum,isFound = 0;
int begin = 0,end = n - 1;
//容錯處理
if(array == NULL || n <= 0){
return 0;
}
while(begin < end){
sum = array[begin] + array[end];
if(sum == m){
isFound = 1;
num1 = array[begin];
num2 = array[end];
break;
}
else if(sum < m){
begin++;
}
else{
end--;
}
}//for
return isFound;
}
int main() {
int i,n,m,num1,num2;
while(scanf("%d %d",&n,&m) != EOF){
array = (int *)malloc(sizeof(int)*n);
//輸入
for(i = 0;i < n;i++){
scanf("%d",&array[i]);
}
int result = FindNum(array,n,m,num1,num2);
//輸出
if(result == 0){
printf("-1 -1\n");
}
else{
printf("%d %d\n",num1,num2);
}
}//while
return 0;
}
最後更新：2017-04-03 14:54:43