[演算法題目] Three Number Sum

本題資訊

難度：medium
使用語言：C++
相關概念：Arrays

題目敘述

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. The function should find all triplets in the array that sum up to the target sum and return a two-dimensional array of all these triplets. The numbers in each triplet should be ordered in ascending order, and the triplets themselves should be ordered in ascending order with respect to the numbers they hold.

If no three numbers sum up to the target sum, the function should return an empty array.

Input:

array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0

Output:
[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

Idea

這一題可以和 Two Number Sum 相互對照。當然最初的想法一定是那個要耗費 \(O(n^3)\) 的解XD 但是如果利用 Two Number Sum 裡面和 Idea 2 類似的想法，應該是可以不用這麼暴力的。另外兩個題目不一樣的點在於一個是只有一組解，這一題是要把所有解列出來，所以我想不到時間上降至線性的做法。

先將 array 從小排到大，依 array 大小執行迴圈，當執行到第 i 個數字時定義 left 是目前位置的下一個位置，right 則從最後一個 index 開始巡覽。每次都把 array[i]、array[left]、array[right] 三個數字相加，並且和 targetSum 做比較，如果比 targetSum 還小，則 left 要再往右邊走，讓下一回合的數字變大，如果比 targetSum 還大，則 right 要往左邊走，讓下一回合的數字變小。重複執行直到 left 大於等於 right。當然如果結果符合 targetSum，就要把這組數字存到 result 內。

以上面做法來說，會需要兩個迴圈作完，因此會有 \(O(n^2)\) 的複雜度，目前我只想到這種方式，不太確定有沒有更好的方法，或是能夠證明這就是最低的時間複雜度。

#include <vector>
using namespace std;

vector<vector<int>> threeNumberSum(vector<int> array, int targetSum) {
  sort(array.begin(), array.end());
  vector<vector<int>> result;
  for (int i = 0; i < array.size() - 2; i++){
    int left = i + 1;
    int right = array.size() - 1;
    while (left < right){
      int tempSum = array[i] + array[left] + array[right];
      if (tempSum == targetSum){
        result.push_back({array[i], array[left], array[right]});
        left++;
        right--;
      } else if (tempSum < targetSum){
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

時間複雜度：\(O(n^2)\)，其中 \(n\) 是 array 的長度。
空間複雜度：\(O(n)\)