題目描述
輸入一個遞增排序的數(shù)組和一個數(shù)字S逞怨，在數(shù)組中查找兩個數(shù)地来，使得他們的和正好是S，如果有多對數(shù)字的和等于S翻伺，輸出兩個數(shù)的乘積最小的喧枷。
輸出描述
對應(yīng)每個測試案例虹统，輸出兩個數(shù)，小的先輸出隧甚。
求解過程
- 首先注意題目要求车荔，數(shù)組是有序，其次要求和相同的要乘積最小那么根據(jù)這兩個信息可以得到一些東西戚扳。
- 數(shù)組有序可以考慮二分（減少時間復(fù)雜度）忧便，和相同要乘積最小那么可以舉個例子來考慮，加如我們需要的和為10帽借，那么可以組成10的數(shù)字分別是1/9,2/8,3/7等等珠增，從這些數(shù)據(jù)中可以看出1/9乘積最小滿足題目中所述，那么可以推導(dǎo)出兩個數(shù)的和相同砍艾，乘積最小的兩個數(shù)字是相隔最遠(yuǎn)的兩個數(shù)
- 根據(jù)上面得出的結(jié)論可以考慮從有序數(shù)組第一個元素開始對數(shù)組遍歷蒂教，只要找到第一對數(shù)那必然是最后的結(jié)果。從下標(biāo)0開始辐董，此時我們假設(shè)當(dāng)前array[i]就是我們要求的結(jié)果中的一個數(shù)悴品，那么另一個數(shù)就應(yīng)該是target=sum-array[i]，現(xiàn)在要做的事就是從下標(biāo)low+1到數(shù)組最后找到是否存在這樣一個數(shù)简烘，存在那么就解決了苔严，不存在那就要繼續(xù)遍歷，是不是經(jīng)典的二分查找了(有序數(shù)組孤澎，下標(biāo)届氢，target)
- 此時還需要考慮當(dāng)我們從左往右遍歷的時候那么右邊的數(shù)字會隨著low下標(biāo)增大，high下標(biāo)的范圍會縮懈残瘛（因為和是固定的）退子，那么我們二分查找的范圍就可以固定到low+1-high之間查找target并返回對應(yīng)下標(biāo)如果查找不成功就返回二分查找中最后的高位下標(biāo)作為下一次循環(huán)的high（下面解釋為什么這么做）
- 如果查找成功那么返回了命中下標(biāo)直接存儲結(jié)果就可以跳出循環(huán)了，但是如果查找失敗我們就會進(jìn)入下一次小的數(shù)固定查找型将，根據(jù)二分查找失敗的條件是低位索引高于了高位索引都沒有命中寂祥，那也就是說當(dāng)前查找失敗的高位索引一定是最靠近target的值，此時我們將高位索引返回雖然會比target小一些七兜，但是因為下一次循環(huán)會增大較小的值丸凭，較大的值根據(jù)和不變也會減小，所以剛好符合要求，將此時二分查找的高位索引作為下一次的high可以加快搜索減少時間復(fù)雜度
解題源代碼
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> result = new ArrayList<>();
if (array==null || array.length==0) return result;
int low = 0;
int high = array.length-1;
while (low<high) {
int rest = sum - array[low];
high = getTarget(array, low+1, high, rest);
if (array[high]!=rest) low++;
else {
result.add(array[low]);
result.add(array[high]);
break;
}
}
return result;
}
private static int getTarget(int[] array, int start, int end, int target) {
int low = start;
int high = end;
while (low<=high) {
int mid = low + (high-low)/2;
if (array[mid]==target) return mid;
else if (array[mid] > target) high = mid-1;
else low = mid+1;
}
//未找到惜犀，將較小的下標(biāo)值返回
return high;
}
}
