题目描述
输入一个递增排序的数组和一个数字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<>();
}
}
这种解法更加简洁,遍历的次数也更少,时间复杂度较低。