和为S的两个数字

题目描述

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

输出描述:

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

解法一：

若循环遍历数组中的每一对数字，时间复杂度为O（n²），不考虑。我们可以通过空间换取时间，遍历数组，利用Map存储(array[i], sum - array[i])。并且在存储array[i]时，可以从Map获取是否存在sum - array[i]，若存在则计算array[i] * (sum - array[i]),利用product存储最小的积，利用a和b存储相应的array[i]与sum - array[i]。</pre>

public class Solution {
    public static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
       Map<Integer, Integer> map = new HashMap<Integer, Integer>();
       ArrayList<Integer> result = new ArrayList<Integer>();
       int a = 0, b = 0, product = Integer.MAX_VALUE;
       boolean set = false;
       for(int i = 0; i < array.length; i++) {
           map.put(array[i], sum - array[i]);
           if(map.containsKey(sum - array[i]) && ((sum - array[i]) * array[i] < product)) {
               a = sum - array[i];
               b = array[i];
               product = (sum - array[i]) * array[i];
               set = true;
           }

       //利用set标志位判断是否更新过a、b，将sum=0时a、b=0与不存在时a、b=0相区分。
       if(set == true) {
           result.add(Math.min(a, b));
           result.add(Math.max(a, b));
       }
       return result;
    }
}

解法二：

很明显解法一没有很好地利用已知条件“递增排序的数组”，我们知道，两个数字的和一样的话，两个数字的差值越大则积越小。又由于数组是有序递增的，我们可以得知，若存在这样的两个数字，则这两个数字一定是所有和为sum的数字中距离最远的。

由此我们可以设置两个指针low和high分别指向数组的开头和结尾，计算array[low]和array[high]，

若array[low]和array[high] == 0，则low和high就是所要求的数字，

若array[low]和array[high] > 0, 则high--，

若array[low]和array[high] < 0, 则low++，

直到low == high

public class Solution {
    public static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(array.length < 1 || array == null)
            return result;
        int low = 0, high = array.length - 1;
        while(low < high) {
            if(array[low] + array[high] == sum) {
                result.add(array[low]);
                result.add(array[high]);
                break;
            }
            else if(array[low] + array[high] > sum) 
                high--;
            else 
                low++;
        }
        return result;
    }
}

时间复杂度为O（n），空间复杂度为O（1），明显优于解法一。

至于为何此时x*y最小，可以证明如下：

image