题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
代码一
思想:双指针从两头遍历,其实最外层的乘积是最小的
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> result=new ArrayList<Integer>();
//边界条件
if(array==null||array.length<=1){
return result;
}
int smallIndex=0;
int bigIndex=array.length-1;
while(smallIndex<bigIndex){
//如果相等就放进去
if((array[smallIndex]+array[bigIndex])==sum){
result.add(array[smallIndex]);
result.add(array[bigIndex]);
//最外层的乘积最小,别被题目误导
break;
}else if((array[smallIndex]+array[bigIndex])<sum){
smallIndex++;
}else{
bigIndex--;
}
}
return result;
}
}
代码二
思想
使用函数,刷题不推荐这种方法
public static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
int temp = 0;
int min = -1;
ArrayList<Integer> arr = new ArrayList<Integer>();
for(int i = 0;i<array.length/2;i++)
{
int find = Arrays.binarySearch(array,i+1,array.length,sum-array[i]);
if(find>0) {
temp = array[i]*array[find];
if(min==-1) {
min = temp;
}
if(temp<=min) {
min = temp;
arr.add(array[i]);
arr.add(array[find]);
}
}
}
Collections.sort(arr);
return arr;
}