合为S的两个数字

题目描述

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

分析

数组是排好序的，我们知道，当两数合相等,S固定。 即(S - x)x = Sx - x^2，x越小，乘积越大。那么就可以使用两头相逼的方法，使左边的数尽可能的小，右边的尽可能的大。

实现

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(array == null || array.length < 2 || array[array.length-1] * 2 -1 < sum || array[0] > sum)
            return result;
        int start = 0, end = array.length-1;
        while(start < end){
            if(array[start] + array[end] == sum){
              result.add(array[start]);
              result.add(array[end]);
              return result;
             }else if(array[start]+array[end]<sum){
                start++;
             }else{
                end--;
             }
        }
        return result;
    }