题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
ArrayList<Integer> a = new ArrayList<Integer>();
int first = 0;
int second = 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < array.length; i++) {
if(array[i] > sum)
break;
if(array[i] > sum - array[i])
break;
int temp = sum - array[i];
if(binarySearch(array, temp)) {
if(array[i] * temp < min){
first = array[i];
second = temp;
min = first * second;
}
}
}
if(first == 0 || second == 0)
return a;
a.add(first);
a.add(second);
return a;
}
private boolean binarySearch(int[] a, int key) {
if(a == null || a.length == 0)
return false;
return search(a, 0, a.length - 1, key);
}
private boolean search(int[] a, int left, int right, int key) {
if(left > right)
return false;
int mid = (left + right) / 2;
if(a[mid] == key)
return true;
if(a[mid] < key)
return search(a, mid + 1, right, key);
else
return search(a, left, mid - 1, key);
}
}
