首页 > ACM题库 > 九度OJ > 剑指offer(17)-和为S的两个数字(九度1352)
2014
02-21

剑指offer(17)-和为S的两个数字(九度1352)

题目描述:

输入一个递增排序的数组和一个数字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

 

刚开始还以为是不是要二分之类的。其实没有那么复杂。

因为是递增数组,所以第一次求出a[low]+a[high]==k,则是乘机最小的那个。因为根据柯西定理还是啥的,当两个数x+y=k,当x和y越接近乘机越大。证明如下:
x+y=k
两边平方:
(x+y)^2=k^2
然后继续变:
(x-y)^2+4xy=k^2
很显然x和y越接近,xy就越大。故让x和y尽量相差很大。
#include <stdio.h>
int main(){
        int n,k,low,high;
        int a[1000000];
        while( scanf("%d%d",&n,&k) != EOF ){
                for( int i=0; i<n; i++){
                        scanf("%d",&a[i]);
                }
                low = 0; high = n-1;
                while( low < high ){
                        if( (a[low]+a[high]) == k ) break;
                        else if( (a[low]+a[high]) > k ) high--;
                        else low++;
                }
                if( low< high ) printf("%d %d\n",a[low],a[high]);
                else printf("-1 -1\n");
        }
    return 0;
}
/**************************************************************
    Problem: 1352
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:1430 ms
    Memory:4856 kb
****************************************************************/

 


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了