題目描述

輸入一個遞增排序的數(shù)組和一個數(shù)字S玄括，在數(shù)組中查找兩個數(shù)，是的他們的和正好是S银锻，如果有多對數(shù)字的和等于S永品，輸出兩個數(shù)的乘積最小的。

輸出描述:
對應(yīng)每個測試案例击纬，輸出兩個數(shù)鼎姐，小的先輸出。

分析：

求和更振，當(dāng)獲得了一個數(shù)字炕桨，另一個應(yīng)該出現(xiàn)的數(shù)字可以通過求差來獲得，因?yàn)槭沁f增排序的數(shù)組肯腕，所以只需要遍歷后續(xù)的數(shù)字即可献宫，如果存在，那么放入ArrayList中進(jìn)行保存实撒，同時把兩者的乘積同時保存一下姊途，這樣方便后面直接取值，而不用每次比較的時候取值再進(jìn)行相乘計(jì)算知态，能節(jié)省一點(diǎn)時間捷兰。

解答：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if (array == null || array.length < 2) {
            return arrayList;
        }
        int len = array.length;
        if (array[len - 1] + array[len - 2] < sum) {
            return arrayList;
        }
        for(int i=0;i<len;i++) {
            int a = array[i];
            int b = sum -a;
            int j = i;
            while (array[j] < b) {
                j++;
            }
            if (array[j] == b) {
                //當(dāng)存在這樣的一個數(shù)值時，若ArrayList為空肴甸，則直接存入寂殉，若不空囚巴，則比較乘積大小原在，判斷是否替代原有值
                if (arrayList == null || arrayList.size()==0) {
                    arrayList.add(0, a);
                    arrayList.add(1, b);
                    arrayList.add(2, a * b);
                }else{
                    if (arrayList.get(2) > a * b) {
                        arrayList.add(0, a);
                        arrayList.add(1, b);
                        arrayList.add(2, a * b);
                    }
                }
            }else{
                continue;
            }
        }
        //返回的時候要把用來存放乘積的位置釋放掉  
        if (arrayList.size() > 0)
            arrayList.remove(2);
        return arrayList;
    }
}

運(yùn)行成功

解法二：

思路：

數(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

時間復(fù)雜度：O(n)

找到的第一組（相差最大的）就是乘積最小的∩蟛校可以這樣證明：
考慮x+y=C（C是常數(shù)）梭域，xy的大小。
不妨設(shè)y>=x搅轿，y-x=d>=0病涨，即y=x+d, 2x+d=C, x=(C-d)/2,
xy=x(x+d)=(C-d)(C+d)/4=(C^2-d2)/4，
也就是xy是一個關(guān)于變量d的二次函數(shù)璧坟，對稱軸是y軸既穆，開口向下。
d是>=0的雀鹃，d越大, xy也就越小幻工。

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
       int i = 0, j = array.length - 1;
        while (i < j) {
            int curSum = array[i] + array[j];
            if (curSum == sum) {
                return new ArrayList<>(Arrays.asList(array[i], array[j]));
            }
            if (curSum < sum) {
                i++;
            }else{
                j--;
            }
        }
        return new ArrayList<>();
    }
}

運(yùn)行成功

這種解法更加簡潔，遍歷的次數(shù)也更少黎茎，時間復(fù)雜度較低囊颅。