# 15. 3Sum

## 題目概要

從陣列中找到三個數，三個數相加等於 0，結果可能有很多個，且同樣三個數無論怎麼排序都算同個結果。

## 解題技巧

1. 首先需要給陣列排序
2. 遍歷陣列從 0 ~ length - 2 (邊界)
3. 如果當前的數字等於前一個數字則跳過這個數(去重)
4. 如果數字不同，則設置 start = i + 1 ; end = length - 1；計算 i, start, end 三個數的和比零大還是小，如果比 0 小 `start++`，如果比 0 大 `end--`，如果等於 0 就把這三個數放進結果裡
5. 返回結果

## 解題流程

1. 舉個例子，假設現在有一陣列為`[-1, 0, 1, 2, -1, -4]`，每一步驟說明如下：

2. 因為剛剛三數相加小於 0 所以 start 往後移一位到 -1，再次相加結果還是相同，所以 `start++`


3. -4 + 0 + 2 還是小於 0，繼續 `start++`


4. 最後 -4 + 1 + 2 還是小於 0，但循環已經結束，所以我們將 `i + 1`：


5. 下一輪開始，`start = i + 1`，end 依然是 `length - 1`


6. (-1)+0+2 比 0 大，所以 `end--`：


7. -1+0+1=0，所以把 `[-1, 0, 1]` 存入結果


步驟依此類推直到全部數字遍歷完畢。

## 程式碼

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let result = [];
    nums.sort((a, b) => a - b); // 首先排序

    for(let i = 0; i < nums.length - 2; i++) {
        if (i === 0 || nums[i] !== nums[i - 1]) {
            let start = i + 1, end = nums.length - 1;
            while(start < end) {
                if (nums[i] + nums[start] + nums[end] === 0) {
                    result.push([nums[i], nums[start], nums[end]]);
                    start++;
                    end--;
                    // 去重
                    while(start < end && nums[start] === nums[start - 1]) {
                        start++;
                    }
                    while(start < end && nums[end] === nums[end + 1]) {
                        end--;
                    }
                } else if (nums[i] + nums[start] + nums[end] < 0) {
                    start++;
                } else { // > 0
                    end--;
                }
            }
        }
    }
    
    return result;
};