# 15. 3Sum

### Leetcode

<https://leetcode.com/problems/3sum/description/>

### 題目

Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`.

Notice that the solution set must not contain duplicate triplets.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [-1,0,1,2,-1,-4]
</strong><strong>Output: [[-1,-1,2],[-1,0,1]]
</strong><strong>Explanation: 
</strong>nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [0,1,1]
</strong><strong>Output: []
</strong><strong>Explanation: The only possible triplet does not sum up to 0.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [0,0,0]
</strong><strong>Output: [[0,0,0]]
</strong><strong>Explanation: The only possible triplet sums up to 0.
</strong></code></pre>

&#x20;

**Constraints:**

* `3 <= nums.length <= 3000`
* `-105 <= nums[i] <= 105`

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

3Sum 只要固定一個數後，剩下的兩個數就是 1. Two sum 的解法，所以我們先用這個方法解解看，但 3Sum 最後要的答案是矩陣中的元素不能重複，所以最後還需要多判斷 3 個值加起的矩陣，是否已經出現過 (`checkNotDuplicate`)

```javascript
var threeSum = function(nums) {
    const output = [];

    const checkIsSame = (arr1, arr2) => {
        for(let i=0; i<arr1.length; i++) {
            if (arr1[i] !== arr2[i]) {
                return false;
            }
        }
        return true;
    }
    const checkNotDuplicate = (arr) => {
        for(let i=0; i<output.length; i++) {
            if (checkIsSame(arr, output[i])) {
                return false;
            };
        }
        return true;
    }

    for (let i=0; i<nums.length; i++) {
        const x = nums[i];
        const map = {};

        for (let j=i+1; j<nums.length; j++) {
            const y = nums[j];
            const z = -(x + y);
            if (map[z] !== undefined) {
                const result = [x, y, z];
                result.sort();

                if(checkNotDuplicate(result)) {
                    output.push(result);
                };
            }
            map[y] = j;
        }
    }

    return output;
};
```

但可惜的是遇到測資 \[0,0,0,0,0,0,0,0,...] 數萬個 0，或是符合結果的 `output` 矩陣數量很多時， `checkNotDuplicate` 的計算會越來越多導致 TLE...

* **方法二 - 排序 + HashTable**

方法一的失敗點在於重複數值的檢查太多遍導致 TLE，要如何把重複數值移掉呢？我們可以採用以下方式：

1. 由小到大先排序過原始矩陣，即 `nums[x] < nums[y] < nums[z]`
2. 在對每個元素處理時，只需要處理第一次出現的元素就好，例如：`[-2, -2, -2, -2, 1, 1]`，只有第一個元素的 `-2` 需要處理，後面不論再出現幾次 `-2` 都可以略過了

```javascript
var threeSum = function (nums) {
    nums.sort((a, b) => a - b);

    const output = [];

    for (let i = 0; i < nums.length; i++) {
        // 步驟 2. 排除後續出現過的元素
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        const x = nums[i];
        const map = {};

        for (let j = i + 1; j < nums.length; j++) {
            // 步驟 2. 排除後續出現過的元素
            if (j - 1 !== i && nums[j] === nums[j - 1]) continue;

            const y = nums[j];
            const z = -(x + y);
            if (map[z] !== undefined) {
                const result = [x, y, z];
                output.push(result);
            }
            map[y] = j;
        }
    }

    return output;
};
```

但將以上這段程式碼拿去跑，會發現有個問題是測資: `[0, 0, 0]` ，如果此時 `i=0, j=1` 當跑到 `if (map[z] !== undefined)` 這行時，因為 `0` 還沒有被加進 map 裡，所以 `if` 的判斷式不會進去，而接著 `i=0, j=2` 以及 `i=1, j=2` 時，因為會排除掉後續出現過的元素，所以迴圈也不會再進去了，最後 output 會錯誤的回傳空矩陣

爲了解決這個問題我們需要改變一下 `map` 參數記錄的邏輯：

1. 把 `map` 從第一個迴圈中移出，改為在最外層記錄 `map`
2. `map` 從原本紀錄 **鍵值對(key, value)** 改為紀錄 **元素的次數**，這樣一來在最後 3 個數相加判斷是否為 0 的時候，可以從 `map` 得知需要用的值是否足夠

   例如：`[-2, 1, 1]`，`map` 會先記錄 `-2` 有一個、`1` 有兩個，前兩個元素計算時根據 `x=-2, y=1` 推斷出 `z=1` ，`y, z` 兩個都需要 `1`，這時查看 `map` 發現裡面 `1` 的數量有兩個是足夠的，所以 `[-2, 1, 1]` 就會是其中一組答案

```javascript
var threeSum = function (nums) {
    nums.sort((a, b) => a - b);

    const output = [];
    const map = {};
    // 先遍歷矩陣一次，記錄所有元素的個數
    for (let i = 0; i < nums.length; i++) {
        const value = nums[i];
        if (map[value] === undefined) {
            map[value] = 1
        } else {
            map[value]++
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        const x = nums[i];

        for (let j = i + 1; j < nums.length; j++) {
            if (j - 1 !== i && nums[j] === nums[j - 1]) continue;

            const y = nums[j];
            const z = 0 - x - y;
            const result = [x, y, z];

            // 預期的元素不在 map 中，可以直接略過
            if (map[z] === undefined) continue;

            let countZ = 1;
            if (x === z) countZ++;
            if (y === z) countZ++;
            // 確認元素的個數足夠 => 答案成立
            if (map[z] >= countZ) {
                output.push(result);
            }
        }
    }

    return output;
};
```

但這樣我們會發現答案還是有重複的

例如：`[-4, -1, -1, 0, 1, 2]`

從第二個元素 `-1` 開始算答案有 `[-1, 0, 1]`

從第四個元素 `0` 開始算答案也有 `[0, 1, -1]`

所以其實我們還需要以下邏輯移除掉重複的答案：

> 以上從第四個元素 `0` 開始算，預期的第三個答案是 `-1`，但這個數已經小於第二個元素 `1`了，由於一開始的矩陣已經由小到大排序過，所以可以知道 `[0, 1, -1]` 一定是個重複的答案了，需要略過

另外由於矩陣已經由小到大排序過，所以答案的 3 個數字正負號會是 `--+` 或是 `-++`, 第一個數字一定不會是正數，所以也可以略過第一個元素大於 0 的狀況優化執行速度

```javascript
var threeSum = function (nums) {
    nums.sort((a, b) => a - b);

    const output = [];
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        const value = nums[i];
        if (map[value] === undefined) {
            map[value] = 1
        } else {
            map[value]++
        }
    }

    for (let i = 0; i < nums.length; i++) {
        // 排除第一個數字為正數的狀況，優化執行速度
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        const x = nums[i];

        for (let j = i + 1; j < nums.length; j++) {
            if (j - 1 !== i && nums[j] === nums[j - 1]) continue;

            const y = nums[j];
            const z = 0 - x - y;
            const result = [x, y, z];

            // 因為矩陣由小到大排序，排除第三個元素小於第二個元素的重複答案
            if (z < y) continue;
            if (map[z] === undefined) continue;

            let countZ = 1;
            if (x === z) countZ++;
            if (y === z) countZ++;
            if (map[z] >= countZ) {
                output.push(result);
            }
        }
    }

    return output;
};
```

Runtime: 261 ms Beats 22.75% of users with JavaScript

Memory: 67.37 MB Beats 10.12% of users with JavaScript

**參考資料**

Solution 1. Hashtable

{% embed url="<https://zxi.mytechroad.com/blog/two-pointers/leetcode-15-3sum/>" %}

* **方法三 - 排序 + Two pointers**

由於打算把原始的矩陣由小到大排序過，所以在找 **第二(y)** 及 **第三(z)** 個數字時可以使用 **雙指針的方式(`l` 代表左、`r` 代表右)** 求出來，這裡有幾個需要注意的地方：

1. 由於答案要排除重複數組，所以在找到答案後，如果 `l+1` 的元素跟 `l` 的元素一樣的話，要繼續往右邊的下一個元素 `l+2` 找 (`r` 也是同樣的道理)

```javascript
var threeSum = function (nums) {
    nums.sort((a, b) => a - b);

    const output = [];

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

        const x = nums[i];

        let l = i + 1;
        let r = nums.length - 1;
        while (l < r) {
            const y = nums[l];
            const z = nums[r];
            if (x + y + z === 0) {
                output.push([x, nums[l], nums[r]]);
                // 找到答案後如果下一個數字一樣，繼續往右找
                while (l < r && nums[l + 1] === nums[l]) {
                    l++;
                }
                while (l < r && nums[r - 1] === nums[r]) {
                    r--;
                }
                l++;
                r--;
            } else if (x + y + z > 0) {
                r--;
            } else {
                l++;
            }
        }
    }

    return output;
};
```

Runtime: 145 ms Beats 88.80% of users with JavaScript

Memory: 64.37 MB Beats 62.95% of users with JavaScript

**參考資料**

{% embed url="<https://ithelp.ithome.com.tw/articles/10277494>" %}
