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


解题思路

和上一题思路差不多,左右加逼,要注意的是:最小乘积一定是最外围两个数相乘!

证明如下,假设 b > a,且存在
a + b = s
(a - m) + (b + m) = s
则 (a - m) * (b + m) = ab - (b - a) * m - m * m < a * b

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

内容来源于网络如有侵权请私信删除