[演算法題目] Two Number Sum

本題資訊

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

---

題目敘述

這題是99.9%的人進行刷題的第1題……吧。

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.

Note that the target sum has to be obtained by summing two different integers in the array; you can’t add a single integer to itself in order to obtain the target sum. You can assume that there will be at most one pair of numbers summing up to the target sum.

現在有一組array和目標值，找出array中相加等於目標值的兩個元素。題目提到我們可以假設最多只有一組符合的答案。

例如我現在有一個array是 [3, 5, -4, 8, 11, 1, -1, 6]，目標值是10。肉眼看應該不難發現11 + (-1) = 10，return回來的會是[11, -1]。

另外題目假定我們不需要考慮一組以上的解，因此解法上會變得更容易一點點。

Idea 1

不愧是easy中的第一題，光看到題目就蠻直覺，但通常直覺想到的解法複雜度也蠻高。

設定兩個迴圈，第一個迴圈是走過array每個元素（設定目前走到的index為i），每遇到一個元素，執行第二個迴圈將array的元素從頭走過一遍（設定目前走到的index為j）。兩個迴圈中目前走到的元素相加，若有符合目標 (target_sum) 則回傳。

#include <vector>
using namespace std;

vector<int> twoNumberSum(vector<int> array, int targetSum) {
  // Write your code here.
	for (int i = 0; i < array.size(); i++){
		for (int j = i + 1; j < array.size(); j++){
			if (array[i] + array[j] == targetSum){
				return vector<int>{array[i], array[j]};
			}
		}
	}
  return {};
}

時間複雜度：\(O(n^2)\)
空間複雜度：\(O(1)\)

Idea 2

雖然這題難度歸類是簡單的，但我覺得只是容易想出初步想法。考慮到 \(O(n^2)\) 的時間複雜度還是蠻高，這題看能不能用其它的處理方式，少一個迴圈。

array 題目的處理方式不外乎那幾種：先排序、設定 index 或是迭代條件、從頭尾著手處理等等。本想法中我們一樣先將原始的陣列由小到大排序，並且從頭以及尾巴的數字開始，由於希望能將兩數的合等於 targetSum，因此若目前的兩個數的合小於 targetSum，就把左手邊（頭）開始的 index 再往後一格，增大數字看合有沒有符合；相反的，若目前的兩個數的合大於 targetSum，就把右手邊（尾）開始的 index 再往前一格，縮小一些數字的值看能不能符合。

#include <vector>
using namespace std;

vector<int> twoNumberSum(vector<int> array, int targetSum) {
  sort(array.begin(), array.end());
  int left = 0;
  int right = array.size() - 1;
  while(left < right){
    int current = array[left] + array[right];
    if (current == targetSum){
      return {array[left], array[right]};
    } else if (current < targetSum){
      left++;
    } else {
      right--;
    }
  }
  return {};
}

時間複雜度：\(O(n\log n)\)
空間複雜度：\(O(1)\)

Idea 3

再來是另外一個想法，會用到比 Idea 2 多的空間，但時間複雜度可以再降一些。

主要是利用 unordered_set 和這個題目特性。因為我已經有了 target_sum、也有原先 array 裡面目前跑到的數字，那麼我想要找另外一個數字（也就是兩個數字的差）其實是一件很容易的事情吧！雖然需要多一個空間儲存無法配對的數字，但不用再另外排序，可以將時間複雜度降成線性。

#include <vector>
#include <unordered_set>
using namespace std;

vector<int> twoNumberSum(vector<int> array, int target_sum){
  unordered_set<int> set;
  for (int num: array){
    int match = target_sum - num;
    if (set.find(match) != set.end()){
      return vector<int>{match, num};
    } else {
      set.insert(num); //沒辦法配對的數字先暫存在一個地方
    }
  }
  return {};
}

時間複雜度：\(O(n)\)
空間複雜度：\(O(n)\)