和为 S 的两个数字

输入一个递增排序的数组和一个数字 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; } }