题目描述:
输入一个递增排序的数组和一个数字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的两个数字
* 来源:http://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;
}
分享到:
相关推荐
《剑指Offer》 1. 赋值运算函数 2. 单例设计模式 3. 二维数组中查找目标值 4. 替换字符串中的空格 5. 从尾到头打印链表 6. 由前序和中序遍历重建二叉树 7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. ...
剑指 Offer 57. 和为s的两个数字标签:数组、双指针、二分查找难度:简单题目大意给定一个升序数组 nums,以及一个目标整数 target。要求:在数组
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
剑指Offer(Python多种思路实现):和为s的数字 面试57题: 题目:和为s的数字 题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积...
翻转单词顺序列,反转链表,斐波那契数列,复杂链表的复制,构建乘积数组,和为s的连续整数序列,和为s的两个数字,滑动窗口的最大值,机器人的运动范围,剑指offer-python实现.docx,矩形覆盖,矩阵中的路径,连续子数组的最大...
1、剑指解析 2、代码实现 class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: if len(nums)target or nums[j]+nums[j-1]<target: return [] while i<j: if nums[i]+nums[j]...
和为s的两个数字 9、57-II. 和为s的连续正数序列 10、 58-I. 翻转单词顺序 11、58-II. 左旋转字符串 12、66. 构建乘积数组 二、栈和队列 1、06. 从尾到头打印链表 2、09.用两个栈实现队列 3、30.包含min函数的栈 4、...
解析:这道题一开始看的时候,有点类似于《剑指offer》的面试题57:和为s的数字。 这那道题中,数组时排序数组,设置两个指针,分别指向头和尾。 当两者之和大于s时,把尾指针向前移;当两者之和小于s时,把头指针向...
剑指offer 第2版 Title-Link Describe Method Note 03 数组中重复的数字 长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内,找出数组中任意一个重复的数字 数组 HashSet 1 04 二维数组中的查找 在一个 n * m ...
1. 题目 编写一个方法,计算从 0 到 n (含 n) 中数字 2 出现的次数。 示例: 输入: 25 输出: 9 解释: (2, 12, 20, 21, ...同题:剑指Offer – 面试题43. 1~n整数中1出现的次数(找规律+公式) 按位遍历每个位,例如521