剑指offer 42.和为S的两个数字

题目描述

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

输出描述:

对应每个测试案例，输出两个数，小的先输出。

思路：

两个指针，分别从前后同时扫描数组，如果和大于 sum, 后面的数组往中间移一个，如果小于 sum, 前面的数组往中间移一位
这题主要要注意第一次碰到相加等于 sum 的两个数的乘积就是最小的，不能被题目坑了

找到的第一组（相差最大的）就是乘积最小的。
可以这样证明：https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b?f=discussion
考虑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 static ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(array == null || array.length == 0){
            return list;
        }

         // 其实第一次碰到相加等于 sum 的两个数的乘积就是最小的，不能被题目坑了

        // 两个指针，分别从前后同时扫描数组
        int i = 0, j = array.length - 1;
        int a = 0, b = 0;
        int mul = 1 << 30;
        while(i < j){
            // 如果和大于 sum, 后面的数组往中间移一个
            int temp = array[i] + array[j];
            if(temp == sum){
                list.add(array[i]);
                list.add(array[j]);
                break;
            }else if(temp > sum){
                j--;
            }else{
                i++;
            }
        }
       return list;
    }
}