题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
分析：
求和，当获得了一个数字，另一个应该出现的数字可以通过求差来获得，因为是递增排序的数组，所以只需要遍历后续的数字即可，如果存在，那么放入ArrayList中进行保存，同时把两者的乘积同时保存一下，这样方便后面直接取值，而不用每次比较的时候取值再进行相乘计算，能节省一点时间。
解答：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
if (array == null || array.length < 2) {
return arrayList;
}
int len = array.length;
if (array[len - 1] + array[len - 2] < sum) {
return arrayList;
}
for(int i=0;i<len;i++) {
int a = array[i];
int b = sum -a;
int j = i;
while (array[j] < b) {
j++;
}
if (array[j] == b) {
//当存在这样的一个数值时，若ArrayList为空，则直接存入，若不空，则比较乘积大小，判断是否替代原有值
if (arrayList == null || arrayList.size()==0) {
arrayList.add(0, a);
arrayList.add(1, b);
arrayList.add(2, a * b);
}else{
if (arrayList.get(2) > a * b) {
arrayList.add(0, a);
arrayList.add(1, b);
arrayList.add(2, a * b);
}
}
}else{
continue;
}
}
//返回的时候要把用来存放乘积的位置释放掉
if (arrayList.size() > 0)
arrayList.remove(2);
return arrayList;
}
}
运行成功
解法二：
思路：
数列满足递增，设两个头尾两个指针i和j，
若ai + aj == sum，就是答案（相差越远乘积越小）
若ai + aj > sum，aj肯定不是答案之一（前面已得出 i 前面的数已是不可能），j -= 1
若ai + aj < sum，ai肯定不是答案之一（前面已得出 j 后面的数已是不可能），i += 1
时间复杂度：O(n)
找到的第一组（相差最大的）就是乘积最小的。可以这样证明：
考虑x+y=C（C是常数），xy的大小。
不妨设y>=x，y-x=d>=0，即y=x+d, 2x+d=C, x=(C-d)/2,
xy=x(x+d)=(C-d)(C+d)/4=(C2-d2)/4，
也就是xy是一个关于变量d的二次函数，对称轴是y轴，开口向下。
d是>=0的，d越大, xy也就越小。
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
int i = 0, j = array.length - 1;
while (i < j) {
int curSum = array[i] + array[j];
if (curSum == sum) {
return new ArrayList<>(Arrays.asList(array[i], array[j]));
}
if (curSum < sum) {
i++;
}else{
j--;
}
}
return new ArrayList<>();
}
}
运行成功
这种解法更加简洁，遍历的次数也更少，时间复杂度较低。
