题目
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
分析
这个题目最容易想到的就是先固定一个数，然后将这个数分别和数组中的每个元素相加，符合要求的加入到list中，然后后移固定的这个数，再从数组开头一次和这个数相加 。这样是可以找出所有的复合要求的组合的。这个算法有两层嵌套，时间复杂度是O(n2)。
还有一种我们称之为“夹逼”的方法，设置两个指针，分别指向数组的第一个元素和最后一个元素。
假如这两个数的和小于S，因为数组是有序的，就将第一个指针后移。
假如这两个数的和大于S，因为数组是有序的，就将最后一个指针前移。
跳出条件是两个指针重合或者第一个指针>后一个指针。
运用这个方法，还有一个好处就是，第一次找到的组合就是相乘后积最小的。
代码
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList <Integer> resultList = new ArrayList<>();
if(array == null || array.length < 2){
return resultList;
}
// 指向第一个数的指针
int first = 0;
// 指向最后一个数
int last = array.length -1;
// 假如两个数的和大于sum，后面的数前移，假如两个数的和小于sum，前一个数后移，直到两个数相遇
int tempSum = 0;
while(first < last){
tempSum = array[first] + array[last];
if(tempSum == sum){// 当前两个数的和为sum，添加到数组
resultList.add(array[first]);
resultList.add(array[last]);
return resultList;//这两个数就是乘积最小的，不用再继续找了
}else if(tempSum < sum){
// 和小于sum，前一个数后移
first++;
}else{
last--;
}
}
return resultList;
}
}
