[置顶] 【剑指offer学习】求和为定值的两个数
来源：程序员人生 发布时间：2014-11-04 08:42:21 阅读次数：1868次
- 《神雕侠侣》中的‘剑冢’，收存着‘剑魔独孤求败’生平用过的3把剑：“杨过提起右首第1柄剑，只见剑下的石上刻有两行小字‘凌厉刚猛，无坚不摧，弱冠前以之与河朔群雄争锋’；第2把是玄铁重剑：‘重剑无锋，大巧不工。410岁前恃之横行天下’；第3把则是木剑，剑下的石刻道：‘410岁后，不滞于物，草木竹石都可为剑。自此精修，渐进于无剑胜有剑之境。’。算法的精华也在于此，只有突破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者相差越远，乘积越小。
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
