和为S的两个数字

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

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

方法一
最直观的一个方法就是现在数组中固定一个数字，再依次判断数组中其余的n-1个数字与它的和是不是等于S，复杂度是O($n^2$)。

方法二

分析

我们选择数组中两个数字，如果其和等于S，那么说明我们找到了对的，如果小于S，我们希望两个数字的和在大一点，由于数组已经排好序了，所以选择较小数字后面的数字；同样，如果当两个数字的和大于输入数字的时候，我们可以选择较大数字前面的数字，因为排在数组前面的数字要小一些，所以可以采用左右夹逼法

注意：不要被条件输出两个数的乘积最小的误导。
假设：若b>a,且存在，
a + b = s;
(a - m ) + (b + m) = s
则：(a - m )(b + m)=ab - (b-a)m - m*m < ab；说明外层的乘积更小。

代码：

	public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
		ArrayList<Integer> list  = new ArrayList<Integer>();
		if(array == null || array.length <= 1) {
			return list;
		}
		//设置两个指针分别指在数组头和数组尾
		int low = 0, high = array.length - 1;
		while(high > low) {
			//当第一次找到合适的数字时处于所有合适数字的最外层，通过上面的证明其乘积也是最小的
			if(array[low] + array[high] == sum) {
				list.add(0, array[low]);
				list.add(1, array[high]);
				break;
			}
			else if(array[low] + array[high] > sum) {
				high--;
			}
			else {
				low++;
			}
		}
		
		return list;

	}