和為S的兩個數(shù)字
題目描述
輸入一個遞增排序的數(shù)組和一個數(shù)字S，在數(shù)組中查找兩個數(shù)，是的他們的和正好是S捏雌，如果有多對數(shù)字的和等于S，輸出兩個數(shù)的乘積最小的笆搓。
輸出描述:
對應(yīng)每個測試案例性湿，輸出兩個數(shù)纬傲，小的先輸出。
import java.util.ArrayList;
public class Solution {
/*解題思路：查找
數(shù)列滿足遞增肤频，設(shè)兩個頭尾兩個指針i和j叹括，
若ai + aj == sum，就是答案（距離越遠(yuǎn)乘積越邢摹）
若ai + aj > sum汁雷，aj肯定不是答案之一（前面已得出 i 前面的數(shù)已是不可能），j -= 1
若ai + aj < sum报咳，ai肯定不是答案之一（前面已得出 j 后面的數(shù)已是不可能）侠讯，i += 1
O(n)
*/
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list=new ArrayList<Integer>();
if(array==null||array.length<2){
return list;
}
int i=0;
int j=array.length-1;
while(i<j){
if(array[i]+array[j]==sum){
list.add(array[i]);
list.add(array[j]);
return list;
}else if(array[i]+array[j]>sum){
j--;
}else{
i++;
}
}
return list;
}
}
