題⽬描述

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

返回值描述：對應每個測試案例，輸出兩個數，⼩的先輸出。

輸⼊：[1,2,4,7,11,15],15
返回值：[4,11]

思路及解答

暴⼒遍歷

直接遍歷每兩個數，查看其和是否符合等於 sum ,再計算其乘積，是否⼩於之前的乘積，如果⼩於，則更新。

public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
     ArrayList<Integer> results = new ArrayList<>();
     long mutip = 999999999;
     if (array != null && array.length > 2) {
         for (int i = 0; i < array.length - 1; i++) {
             for (int j = i + 1; j < array.length; j++) {
                 if (array[i] + array[j] == sum && array[i] * array[j] < mutip) {
                     results.clear();
                     results.add(array[i]);
                     results.add(array[j]);
                     mutip = array[i] * array[j];
                 } else if (array[i] + array[j] > sum) {
                     break;
                 }
             }
         }
     }
     return results;
 }

• 時間複雜度：O(n²)，需要檢查所有可能的數對組合

• 空間複雜度：O(1)，只使用常數級別額外空間

  使⽤HashSet

針對每⼀個數字 a ，都查看 hashset 中是否存在 sum-a ，同時把該數字添加到 set 中。如果存在則計算其乘積，更新乘積最⼩值。

public ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) {
     ArrayList<Integer> results = new ArrayList<>();
     long mutip = 999999999;
     HashSet<Integer> set = new HashSet<>();
     if (array != null && array.length > 2) {
         for (int i = 0; i < array.length; i++) {
             if (set.contains(sum - array[i]) && array[i]*(sum - array[i]) < mutip) {
                 results.clear();
                 results.add(sum-array[i]);
                 results.add(array[i]);
                 mutip = array[i] * (sum - array[i]);
             }
             set.add(array[i]);
         }
     }
     return results;
 }

• 時間複雜度：O(n)，只需遍歷數組一次
• 空間複雜度：O(n)，需要HashSet存儲元素

雙指針法（最優）

利用數組有序特性：左右指針分別指向數組首尾，根據當前和動態調整指針位置

由於數組 nums[] 是有序的，也就是第⼀個數字是最⼩的，第⼆個數字是最⼤的，那麼我們使⽤⼀個指針 i 指向數組第⼀個元素，⼀個指針 j 指向數組最後⼀個元素。

i 指針往右邊移動， j 指針往左邊移動，直到兩者相撞（相等）。

如果 nums[i]+nums[j] == sum ,那麼説明這個是可能存在的解，需要計算兩者的乘積，如果⽐保存的乘積還⼩，則更新結果。同時左邊指針 i 往右邊移動⼀位，右邊指針 j 往左邊移動⼀位。

如果 nums[i] + nums[j] > sum ,則説明和太⼤了，⽐ sum 還要⼤，則右邊的指針j需要左移⼀步，即是 j-- 。

如果 nums[i] + nums[j] < sum ,則説明和太⼩了，⽐ sum 還要⼩，則左邊的指針i需要左移⼀步，即是 i++ 。

public ArrayList<Integer> FindNumbersWithSum2(int[] array, int sum) {
     ArrayList<Integer> results = new ArrayList<>();
     long mutip = 999999999;
     if (array != null && array.length > 2) {
         int left = 0,right = array.length-1;
         while(left<right){
             if(array[left]+array[right]==sum){
                 if(array[left]*array[right]<mutip){
                     mutip = array[left]*array[right];
                     results.clear();
                     results.add(array[left]);
                     results.add(array[right]);
                 }
                 left++;
                 right--;
             }else if(array[left]+array[right]>sum){
                 right--;
             }else{
                 left++;
             }
         }
     }
     return results;
 }

• 時間複雜度：O(n)，最壞情況下左右指針共同遍歷整個數組
• 空間複雜度：O(1)，只使用固定數量的指針變量