题目描述
输入一个递增排序的数组和一个数字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
版权声明：本文为博主原创文章，转载请附上博文链接！

奈斯