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


比如数组是{1,2,4,7,8,11,15},求和为15。有4+11=15和7+8=15两组解
  显然可以拿一个数比完一轮后,换下一个数再比一轮,这样的时间复杂度是O(n^2)。所以需要找到更优化的方法。这里需要提到一点:最后的结果可能有很多组,但是题目并没有要求全部求出,因此,求出任意一个解就可以了。
  首先我们思考,如果我们随便拿到了两个数,比如2和15两个数,和为17,而要求和为15,那么我们肯定希望拿到的两个数变小一点,由于数组是递增的,我们可以取15前面的数,再做加法判断,注意到,下次就是2和11,又比15小了,考虑递增的数组,我们要拿一个大一点的数,取2后面的数。然后在判断....因此就需要两个指针,一前一后,帮助移动位置,这样最极端的情况就是两个指针分别从头和尾移动到了中间(用碰到一起可能更准确)就结束,时间复杂度O(n)。
  细节的处理,当数比较大时,是右边前移,数比较小时,是左边后移。
写法:

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;
        }
        int first = 0;
        int last = array.length-1;
        while(first < last){
            //如果相等就放进去
             if((array[first]+array[last])==sum){
                list.add(array[first]);
                list.add(array[last]);
                break;//找到一组解就可以出去了
               }else if((array[first]+array[last])<sum){//小于就移动first,找大数
                first++;
               }else{//大于就移动last,找小一点的数
                last--;
             }
        }
        return list;
    }
}