和为S的两个数字

1.题目：
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。对应每个测试案例，输出两个数，小的先输出。
2.思路：
这道题关键在于递增与乘积最小。首先，递增表示数字没有重复，并且是从左往右增大；其次，乘积最小，不难证明两个数字相差越大，乘积越小，证明如下：

若a+b=s;则有(a+m)+(b-m)=s;假设b>a，则使得f=(a+m)*(b-m)最小。f=ab-(b-a)m-m^2可以看出，要使得fmin,则b与a的差越大越好。

所以：
方法一：夹逼法

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer>result=new ArrayList<Integer>();
        if(array==null||array.length==0){//判空
            return result;
        }
        int left=0;//左边
        int right=array.length-1;//右边
        while(left<right){//两边夹逼，直到重合跳出
            int temp=array[left]+array[right];
            if(temp<sum){//比目标值小
                left++;//增大
            }else if(temp>sum){//比目标值小
                right--;//减小
            }else if(temp==sum){//目标值
                result.add(array[left]);
                result.add((array[right]));
                return result;
            }
        }
        return result;
    }
}

方法二：哈希法
先读题，发现递增的话不会有重复数字，如果有多对数字的和为s，可以用数学证明一个最小的数和最大的数的乘积是最小的，比如1，3和2，2。所以输出的时候我们只用考虑找到第一个最小的数就行了，不用担心排序的问题。

import java.util.ArrayList;
import java.util.HashMap;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer>result=new ArrayList<Integer>();
        if(array==null||array.length==0){//判空
            return result;
        }
        HashMap<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            map.put(i,array[i]);//将数组中的数全部存入map中
        }
        for(int i=0;i<array.length;i++){
            if(map.containsValue(sum-array[i])){//已知a数，判断是否存在b数
                result.add(array[i]);
                result.add(sum-array[i]);
                break;//其实找到的第一组就是乘积最小的
            }
        }
        return result;
    }
}