Day 05 : 来点不一样的 Two Sum

今天来稍微改变一下 Two Sum 这题题目
原本的题目要回传nums中的index，我们来把他改成回传原数吧！

题目：
给一个元素皆不同的阵列以及目标的总和，写一个函式回传阵列，内含两个数总和恰为目标数，且两数不可以同一个元素，答案顺序可和原本阵列不同，可以假设最多只有一组解，若没有找到任何解则回传空阵列

废话不多说直接来个大家一定会用的暴力解！也就是检查每个已知的元素，依序检查，把目标总和减去当下被检查的数，往後依序检查

时间复杂度：Ｏ(n^2)
空间复杂度：Ｏ(1)

function twoNumberSum(array, targetSum) {
  for (let i = 0; i < array.length - 1; i++) {
    let first = array[i];
    for (let j = i + 1; j < array.length; j++) {
      const second = array[j];
      if (first + second === targetSum) {
        return [first, second];
      }
    }
  }
  return [];
}

想办法优化吧！

利用hashTable，虽然多花了Space-> Ｏ(n)
但是时间复杂度可以降到 Ｏ(n)

hashTable 可以让我们在常数的时间Ｏ(1)来取得我们要的数
在javascript可以直接宣告一个{}来使用

举个例子来说
Input：array = [3, 5, -4, 8, 11, 1, -1, 6],
target = 10

我们的目标总和为10
也就是x+y = 10

依序拜访array
step1: 取出3，也就是把x设为３，则 y = 7

看看我们的hashTable是否有 7 ? 发现没有，就把3当作key放到hashTable内，并把value设为true → 3: true, 依序做一样的操作...
直到我们做到了-1，会发现目前hashTable如下

{ 3: True, 5:True, -4:True, 8:True, 11:True, 1:True}

y = 10 -(-1)=11

可以看到11在hashTable！
我们把[-1, 11]放到array 得到我们的答案

时间复杂度为O(n) ，n也就是input array的长度，因为我们只需要依序拜访这个array一次，并计算y (constant time)，并且在hashTable中取得y也只用constant time

此外space也是O(N) → 看我们的hashTable就可以知道
有没有明显感受出和暴力法的差异?

function twoNumberSum(array, targetSum) {
  const hashTable = {};
  for (const x of array) {
    const y = targetSum - x;
    if (y in hashTable) {
      return [x, y];
    } else {
      hashTable[x] = true;
    }
  }
  return [];
}

除了这个方法外，还有另一个优於暴力法的方式。
就是先把array做sort（好的排序方式如Quick sort, Merge sort, Heap Sort）→ 花 O(nlogn)
排序好後就可以在O(n)的时间内找到目标总和，且不需要额外的空间来储存 space O(1)

Sorted Input array :[ -4, -1, 1, 3, 5, 6, 8, 11],
target = 10

假设我们有一个左箭头(left pointer)指到第一个element，right point指到最後一个element

把 -4 + 11 = 7
然後我们发现７< 10 (目标)

如果我们现在去移动右边指标，被加的数就会变小了更不会接近10
所以我们应该移动left pointer
也就是 -1 + 11 (不小心得到答案了)

同理如果我们今天target = 1２那我们应该怎麽移动指标?
继续移动左指标对吧？
1+11
那如果没有找到的时候就是左右两个指标相遇
其实LeetCode也有一道类似题: Two Sum II - Input array is sorted

Time : O(nlogn)+O(n) = O(nlogn)

function twoNumberSum(array, targetSum) {
  array.sort((a, b) => a - b);
  let leftPointer = 0;
  let rightPointer = array.length - 1;
  while (leftPointer < rightPointer) {
    const tmpSum = array[leftPointer] + array[rightPointer];
    if (tmpSum === targetSum) {
      return [array[leftPointer], array[rightPointer]];
    } else if (tmpSum < targetSum) {
      leftPointer++;
    } else {
      rightPointer--;
    }
  }
  return [];
}

相信看到这里，原本的Two sum题目一定难不倒你，也别忘了自己试试喔！
其实後面用了左右指标先来看这题题目是为了先熟悉一下明天的题目

明日题目预告：3Sum