和为S的两个数字

电玩女神 2022-06-07 02:44 116阅读 0赞

链接：[https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b][https_www.nowcoder.com_questionTerminal_390da4f7a00f44bea7c2f3d19491311b]  
来源：牛客网

*  热度指数：72181 时间限制：1秒空间限制：32768K

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得它们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

**输出描述:**`对应每个测试案例，输出两个数，小的先输出。`

分析：思路和[167. Two Sum II - Input array is sorted][]类似，不过这道题和为S的可能有多对数字，要返回乘积最小的两个数字，且将结果放在ArrayList中。刚开始的思路是：定义两个遍历分别指向该数组初始位置0和末尾位置array.length - 1，定义两个数的乘积pow = Integer.MAX\_VALUE，初始值为最大值。然后前后遍历数组，直到i<j，当前后索引i,j对应的数字之和等于s时，判断两个数的乘积是否小于pow，若是，则将这两个数字存入arrayList，直至循环结束，arrayList中的值即为最终结果。但是这样提交后出现超时问题。

后来一想，因为数组的数字是递增的，因为是从前后找这两个数，找到的第一组（相差最大的）就是乘积最小的，就可结束查找，返回结果。证明如下：假设存在两组数：（a,d)、(b,c)，其和都等于S。即a+d = b+c = S，且满足a<b<c<d，可证：ad < bd。

证明步骤如下：d-a>c-b,得(d-a )^2>( c-b)^2，d^2+a^2-2ad+4ad+4bc>c^2+b^2-2bc+4ad+4bc(不等式两边加上4ad+4bc)，得(a+d)^2+4bc>(b+c)^2+4ad，又(a+d)^2 = (b+c)^2，所以得出ad<bc，但这只是针对数组中得数都为非负数不存在负数时才成立得。

之后在讨论区看到了一种更好得证明方法，证明对正负数，”找到的第一组（相差最大的）就是乘积最小的“这一结论仍然成立  
参考（作者：马客(Mark)）：链接：[https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b][https_www.nowcoder.com_questionTerminal_390da4f7a00f44bea7c2f3d19491311b]  
考虑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也就越小。

import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            //if(array.length < 2 || array == null)
                //return arrayList;
            //int pow = Integer.MAX_VALUE;
            int i = 0;
            int j = array.length - 1;
            while(i < j){       
                if(sum == array[i] + array[j]){
                    //if(pow > array[i] * array[j]){
                        //pow = array[i] * array[j];
                        //arrayList.clear();
                        arrayList.add(array[i]);
                        arrayList.add(array[j]);
                        break;
                    //}
                }else if(sum > array[i] + array[j])
                    i++;
                else
                    j--;
            }
            return arrayList;
        }
    }

[https_www.nowcoder.com_questionTerminal_390da4f7a00f44bea7c2f3d19491311b]: https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b
[167. Two Sum II - Input array is sorted]: http://blog.csdn.net/wust_lh/article/details/78157481