JZ57 和為S的兩個數字

題目

輸入一個升序數組 array 和一個數字S，在數組中查找兩個數，使得他們的和正好是S，如果有多對數字的和等於S，返回任意一組即可，如果無法找出這樣的數字，返回一個空數組即可。

方法1 暴力解題

思路

演算法實現

兩次迴圈，兩個值相加與sum進行比較，為true直接break即可

代碼

package mid.JZ57和為S的兩個數字;

import java.util.ArrayList;
public class Solution {
    /**
     * 暴力計算
     * @param array
     * @param sum
     * @return
     * 運行時間     1084ms
     * 占用記憶體     28348KB
     */
    private ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        if(array.length == 0) return res;
        for(int i = 0; i < array.length; i++) {
            for(int j = 0; j < array.length; j++) {
                if(array[i] + array[j] == sum) {
                    res.add(array[i]);
                    res.add(array[j]);
                    return res;
                }
            }
        }
        return res;
    }
}

方法2 雙指針

思路

演算法實現

這道題目還有一個條件是數組是升序序列，在方法一中沒有用到。這個條件有什麼用？
既然數組是有序的，那我們肯定知道和找到一定程度就不找了，我們為什麼要從最小的兩個數開始相加呢？
我們可以用二分法的思路，從中間開始找。

使用雙指針指向數組第一個元素和最後一個元素，然後雙指針對撞移動，如果兩個指針下的和正好等於目標值sum，那我們肯定找到了，如果和小於sum，說明我們需要找到更大的，那隻能增加左邊的元素，如果和大於sum，說明我們需要找更小的，只能減小右邊的元素。

具體做法：

step 1：準備左右雙指針分別指向數組首尾元素。
step 2：如果兩個指針下的和正好等於目標值sum，則找到了所求的兩個元素。
step 3：如果兩個指針下的和大於目標值sum，右指針左移；如果兩個指針下的和小於目標值sum，左指針右移。
step 4：當兩指針對撞時，還沒有找到，就是數組沒有。

代碼

package mid.JZ57和為S的兩個數字;

import java.util.ArrayList;
public class Solution {
    /**
     * 雙指針
     * @param array
     * @param sum
     * @return
     * 運行時間
     * 250ms
     * 占用記憶體
     * 27188KB
     */
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        int left = 0, right = array.length - 1;
        while(left < right) {
            if (array[left] + array[right] == sum) {
                res.add(array[left]);
                res.add(array[right]);
                return res;
            } else if (array[left] + array[right] < sum){
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}