Day 06：3 Sum

在Two Sum 中 我们一开始最初的想法是用2次的loop检查，那换做这3 Sum我们当然可以用三次loop来解，
时间复杂度直接飙升到Ｏ(n^3)。

还记得我们昨天最後一个方式吗?
其实就是利用昨天用到的左右指针的方式。

举一个Input Array: [12, 3, 1, 2, -6, 5, 0, -8, -1]
Target Sum: 0

如果以这题为例子，先把要检查的阵列设定为
1.不是空阵列
2.阵列中每数都不同
来思考这题题目。

step1: 我们一样先将阵列排序
step2: 从阵列的第一个数为主，依序找剩下的数中，可以照到两个数和第一个数相加，最後达到目标总和

以下面例子来说

当我们把排序後的阵列开始检查（也就是这里的-8）
我们先把第一个数 -8 当作基准，往後(-6)开始寻找，开始找出两个数，可以符合加上-8可以变成目标总和（0）

我们把左指标放在第一个基准数右边，右指标一样放在最後面。
以第一次来说，
我们可以得到 sum = -8 + -6 + 12 = -2
这个时候我们可以知道 -2 < 0
代表我们需要移动的是左指标，才可以加上更大的数，让总和更接近0。
因为我们已经排序过这个阵列了

那如果我们遇到相加恰好等於目标总和时，应该要怎麽做？
这题题目要我们要找到所有符合的答案,而非一找到就停止，
所以我们应该要把左指标跟右指标一起移动才对，
这样对於实作程序码是不是有想法了？

那我们来讨论一下时间复杂度吧！

我们知道要从第一个数开始去检查到最後面的数，
而每次的基准数检查都一样要去确认剩下的数找出符合的两数，
所以时间复杂度为Ｏ(n^2)
空间的复杂度上，因为我们一开始都需要把原本得阵列做排序来使用，
所以空间复杂度Ｏ(n)

如果我们依照上面的想法来实作，程序码如下:

function threeNumberSum(array, targetSum) {
    array.sort((a, b) => a - b);
    const triplets = [];
    for (let i = 0; i < array.length - 2; i++) {
      let left = i + 1;
      let right = array.length - 1;
      while (left < right) {
        const sum = array[i] + array[left] + array[right];
        if (sum === targetSum) {
          triplets.push([array[i], array[left], array[right]]);
          left++;
          right--;
        } else if (sum < targetSum) {
          left++;
        } else if (sum > targetSum) {
          right--;
        }
      }
    }
    return triplets;
  }

不过这样的解法可行的前提是，我们假设原本的阵列每一个数都不一样。
而以Leetcode这题来说，targetSum = 0 ，所以如果排序完的第一个数是大於0的，
我们其实就可以完全不用继续检查了!
且“Notice that the solution set must not contain duplicate triplets.”
-> 不可以含重复的triplets

所以我们要多两步检查
1.重复的基准数要跳过
2.左右指针要移动的时候要先检查下个数有没有和自己一样 -> 如果一样，就要在往前多走一步

完整答案的做法如下：

var threeSum = function (nums) {
    nums.sort((a, b) => a - b);
    const triplets = [];

    for (let i = 0; i < nums.length - 2; i++) {
      if (nums[i] > 0) break;
      if (i > 0 && nums[i] === nums[i - 1]) continue;
      let left = i + 1;
      let right = nums.length - 1;
      while (left < right) {
        const sum = nums[i] + nums[left] + nums[right];
        if (sum === 0) {
          triplets.push([nums[i], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < 0) {
          left++;
        } else if (sum > 0) {
          right--;
        }
      }
    }
    return triplets;
  };

明日题目预告:
Squares of a Sorted Array