和为S的两个数字

题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。对应每个测试案例，输出两个数，小的先输出。

思路：数列满足递增条件，设两个头尾指针i和j，若ai + aj == sum，则是答案（相差越远乘积越小）。若ai + aj > sum，则i++后会增大和，只能

j--来减小和。若ai + aj < sum，则j--后会减小和，只能i++来减小和。

时间复杂度：O(n)。

Java代码：

import java.util.List;
import java.util.ArrayList;public class Solution {public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> list = new ArrayList<Integer>();if (array == null || array.length <= 1) {return list;}for (int i = 0, j = array.length - 1; i < j; ) {if (array[i] + array[j] == sum) {list.add(array[i]);list.add(array[j]);break;}while (i < j && array[i] + array[j] > sum) {j--;}while (i < j && array[i] + array[j] < sum) {i++;}}return list;}
}