[劍指offer] 和為S的兩個數字

本文首發于我的個人部落格： 尾尾部落

題目描述

輸入一個遞增排序的數組和一個數字S，在數組中查找兩個數，使得他們的和正好是S，如果有多對數字的和等于S，輸出兩個數的乘積最小的。

解題思路

法一：哈希法。用一個HashMap，它的 key 存儲數S與數組中每個數的差，value 存儲目前的數字，比較S=15, 目前的數為 4，則往 hashmap 中插入(key=11, value=4)。我們周遊數組，判斷hashmap 中的 key 是否存在目前的數字，如果存在，說明存在着另一個數與目前的數相加和為 S，我們就可以判斷它們的乘積是否小于之前的乘積，如果小的話就替換之前的找到的數字，如果大就放棄目前找到的。如果hashmap 中的 key 不存在目前的數字，說明還沒有找到相加和為 S 的兩個數，那就把S與目前數字的差作為 key，目前數字作為 value 插入到 hashmap 中，繼續周遊。

法二：左右夾逼的方法。a+b=sum，a和b越遠乘積越小，因為數組是遞增排序，是以一頭一尾兩個指針往内靠近的方法找到的就是乘積最小的情況。

若ai + aj == sum，就是答案（相差越遠乘積越小）

若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;
    }
}