【上海校区】算法题(二十八):和为S的两个数

python 未结 0 91
什么是网络营销
什么是网络营销 2021-07-22 14:45
悬赏:80
题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

分析
在数组的头部(H)和尾部(T)开始向内遍历,若H+T小于S,则H肯定不是答案之一,因为不可能有数比T大了;若H+T大于S,则T肯定不是答案之一,因为不可能有数比H小了。而当第一次找到H和T时,这时的H*T也是最小的。

牛客网上解释为:考虑x+y=C(C是常数),x*y的大小。不妨设y>=x,y-x=d>=0,即y=x+d, 2x+d=C, x=(C-d)/2, x*y=x(x+d)=(C-d)(C+d)/4=(C^2-d^2)/4,也就是x*y是一个关于变量d的二次函数,对称轴是y轴,开口向下。d是>=0的,d越大, x*y也就越小。

代码
public class DoubleSum {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] arr = {1,2,9,10};
                findSum(arr, 11);
        }
       
        public static void findSum(int[] arr, int sum){
                int H = 0;
                int T = arr.length-1;
                while(H<T){
                        if(arr[H]+arr[T]==sum){
                                System.out.println(H);
                                System.out.println(T);
                                return;
                        }
                        while(H<T && arr[H]+arr[T]>sum){
                                --T;
                        }
                        while(H<T && arr[H]+arr[T]<sum){
                                ++H;
                        }
                }
        }

}
输出:0,3


---------------------
作者:另一个我竟然存在
来源:CSDN
原文:https://blog.csdn.net/qq_24034545/article/details/84029885
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复