輸入一個遞增排序的陣列和一個數字 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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/186033.html
標籤：其他
上一篇：和為 S 的連續正數序列