剑指OfferJZ42：和为S的两个数字-java版

JZ42：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可

首先在数组中找到两个数和为数字S的 在递增排序的数组中，（如果不是有序数组需要变成有序的有利于查找） 设置两个指针，首（左）指针l和尾（右）指针r，分别位于数组的头部和尾部 在查找的过程中指针l往右移动（往数值大的方向移动），指针r往左移动（往数值小的方向移动）

• 如果 左指针指向的数+右指针指向的数=数字S，那么同时将左指针往左移（增大数值），右指针往左移（减小数值），继续进行循环操作直到左右指针位置相邻为止
• 如果 左指针指向的数+右指针指向的数数字S，那么将右指针往左移（减小数值），继续进行循环操作直到左右指针位置相邻为止

如图：1+10=11小于S，需要将左指针往右移（增大数值）

• 接着2+10=12等于S，满足条件，将这两个数存起来，同时将左指针往左移（增大数值），右指针往左移（减小数值）
• 接着4+9=13大于S，需要将右指针往左移（减小数值）
• 接着4+8=12等于S，满足条件，将这两个数存起来，同时将左指针往左移（增大数值），右指针往左移（减小数值）
• 接着5+6=11小于S，这时发现左指针和右指针位置相邻，结束循环 查出来满足两个数和等于数字S的有两对，2和10,4和8

接着考虑如果有多对数字的和等于S，返回两个数的乘积最小的 假设在上一步找到的和为S的数组中，其中一个数是x，那么另一个数就是S-x，两个数的乘积就为x*（S-x）= -x2+xS 可以看出两个数的乘积是数学中一个开口向下的二次函数

根据两个数在数组中的位置分布，可以判断出左指针指向的数（x）在S/2的左边，右指针指向的数（S-x）在S/2的右边，图像上的数值代表两个数的乘积 从图中可以看出，S/2左边图像的数值随横坐标的增大而增大，S/2右边图像的数值随横坐标的增大而减小，所以当x离S/2越远（数值越小），S-x离S/2越远（数值越大）时，x和S-x的乘积越大

所以我们可以得出结论：当左指针指向的数x越小，右指针指向的数x越大，也就是我们第一次找到的那对和为S的数字时，这两个数的乘积是最小的 因此在上面查找数组中两个数和为数字S的过程中，如果 左指针指向的数+右指针指向的数=数字S，那么我们就可以直接返回这两个数字，不用再继续查找了 break循环；

 public class jz42{
    public ArrayList FindNumbersWithSum(int [] array, int sum) {
        ArrayList list=new ArrayList();
        int l=0;//头指针
        int r=array.length-1;//尾指针

        while(l