输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是 S，如果有多对数字的和等于 S，输出两个数的乘积最小的
解题思路
和上一题思路差不多，左右加逼，要注意的是：最小乘积一定是最外围两个数相乘！
证明如下，假设 b > a，且存在
a + b = s
(a - m) + (b + m) = s
则 (a - m) * (b + m) = ab - (b - a) * m - m * m < a * b
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> result = new ArrayList<>();
int low = 0, high = array.length - 1;
while(low < high) {
if(array[low] + array[high] == sum) {
result.add(array[low]);
result.add(array[high]);
return result;
} else if(array[low] + array[high] > sum) {
high--;
} else {
low++;
}
}
return result;
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
