# 15.3Sum <span class="tag" data-diff="medium" />
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}

## 題目
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

**Example:**

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

## 思路

我覺得這題頗有<span class='tag' data-diff='hard'></span>的難度QQ雖然他看起來跟第一題一樣，但難度真的天差地遠，一開始我也打算用第一題的hash map解法，花 $O(n^2)$ 的時間紀錄`nums`中兩兩之和與0的差距，再loop過一遍把所有答案找出來。但這個做法有一個大問題，就是會重複，因為`nums`中的數字是可以重複的，由於沒有記錄每個數字在`nums`中出現過幾次，就會不知道可不可以放在tuple中。 加入許多限制條件後，時間花費跟直接用3層迴圈一樣，而且都會TLE，最後沒有辦法只好從Disscussion中找解答。

var threeSum = function(nums) {
    const results = []

    if (nums.length < 3) return results

    nums = nums.sort((a, b) => a - b)

    let target = 0

    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > target) break

        if (i > 0 && nums[i] === nums[i - 1]) continue

        let j = i + 1

        let k = nums.length - 1


        while (j < k) {
            let sum = nums[i] + nums[j] + nums[k]

            if (sum === target) {
                results.push([nums[i], nums[j], nums[k]])

                while (nums[j] === nums[j + 1]) j++
                while (nums[k] === nums[k - 1]) k--

                j++
                k--

            } else if (sum < target) {
                j++

            } else { 
                k--
            }
        }
    }

    return results
    };

一開始如果`nums`沒有到3個element，就直接回傳空array，接著loop過每一個element，去找出該element所需的另外兩個數字。

由於一開始已經sort過，所以當current element大於目標(`0`)的時候，後面在怎麼找，相加都不會等於目標，就可以跳出loop了。

要找出剩下兩個數字，會從sorted array的兩端開始找(`j`、`k`)，如果三者相加剛好等於目標(`0`)，就push進result中，如果比0還小，就讓佐指標前進去找更大的數；若比0還大，讓右指標往左找較小的數。過程中為了加速，可以跳過連續的相同數字，當左右指標相遇後，則搜尋完成，進到下一個iteration去找result。