本文首發(fā)于我的個(gè)人博客：尾尾部落
題目描述
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S帆竹，在數(shù)組中查找兩個(gè)數(shù)绕娘，使得他們的和正好是S，如果有多對數(shù)字的和等于S栽连，輸出兩個(gè)數(shù)的乘積最小的险领。
解題思路
法一：哈希法。用一個(gè)HashMap秒紧，它的 key 存儲(chǔ)數(shù)S與數(shù)組中每個(gè)數(shù)的差绢陌，value 存儲(chǔ)當(dāng)前的數(shù)字，比較S=15, 當(dāng)前的數(shù)為 4熔恢，則往 hashmap 中插入(key=11, value=4)脐湾。我們遍歷數(shù)組，判斷hashmap 中的 key 是否存在當(dāng)前的數(shù)字绩聘，如果存在沥割，說明存在著另一個(gè)數(shù)與當(dāng)前的數(shù)相加和為 S耗啦，我們就可以判斷它們的乘積是否小于之前的乘積凿菩，如果小的話就替換之前的找到的數(shù)字，如果大就放棄當(dāng)前找到的帜讲。如果hashmap 中的 key 不存在當(dāng)前的數(shù)字衅谷，說明還沒有找到相加和為 S 的兩個(gè)數(shù)，那就把S與當(dāng)前數(shù)字的差作為 key似将，當(dāng)前數(shù)字作為 value 插入到 hashmap 中获黔，繼續(xù)遍歷蚀苛。
法二：左右夾逼的方法。a+b=sum玷氏，a和b越遠(yuǎn)乘積越小堵未，因?yàn)閿?shù)組是遞增排序，所以一頭一尾兩個(gè)指針往內(nèi)靠近的方法找到的就是乘積最小的情況盏触。
若ai + aj == sum渗蟹，就是答案（相差越遠(yuǎn)乘積越小）
若ai + aj > sum赞辩，說明 aj 太大了雌芽，j --
若ai + aj < sum，說明 ai 太小了辨嗽，i ++
參考代碼
import java.util.ArrayList;
import java.util.HashMap;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(array.length < 2)
return res;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int less = Integer.MAX_VALUE;
for(int i = 0; i < array.length; i++){
if(map.containsKey(array[i])){
if(array[i] * map.get(array[i]) < less){
less = array[i] * map.get(array[i]);
res.clear();
res.add(map.get(array[i]));
res.add(array[i]);
}
}else{
int key = sum - array[i];
map.put(key, array[i]);
}
}
return res;
}
}
法二：左右夾逼
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(array.length < 2)
return res;
int i = 0, j = array.length - 1;
while(i != j){
if(array[i] + array[j] == sum){
res.add(array[i]);
res.add(array[j]);
break;
}else if(array[i] + array[j] < sum){
i++;
}else{
j--;
}
}
return res;
}
}
