题目描述

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

输出描述:

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

方法一

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

方法二

分析

我们选择数组中两个数字，如果其和等于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
    
      FindNumbersWithSum(int [] array,int sum) {
    		ArrayList
     
       list  = new ArrayList
      
       ();		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;	}