15. 3Sum

📘 題目敘述

給你一個整數陣列 nums。

請回傳所有不重複的三元組 [nums[i], nums[j], nums[k]]，使得：

i != j、i != k、j != k
nums[i] + nums[j] + nums[k] == 0

答案中不可以包含重複的三元組。

條件限制

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

🧠 解題思路

我這份寫法的速度沒有很快，因為是遇到 TLE 之後才加上一些判斷條件修正的😔😔

主體概念是：先排序，然後固定一個數 nums[x]，把問題變成在右邊找兩個數 nums[y]、nums[z] 讓它們加起來等於 -nums[x]。

排序的好處是：

可以在掃描時提早停止：如果 nums[x] > 0，後面都更大，不可能再湊到 0
可以用「從右邊往左縮」的方式調整 z 來逼近目標

另外我有做兩次去重：

第一層固定 x 時，用 before 跳過相同的 nums[x]
產生完所有三元組後，把 ans 再 sort 一次，然後從後往前把相同的三元組 erase 掉

所有變數

ans：存放所有找到的三元組答案
before：記錄上一個使用過的 nums[x]，避免固定 x 時重複處理同樣的值
z：右側指標，從最右邊往左移動
check：在最後去重時記錄上一個三元組，判斷是否重複

🪜 主要流程步驟

1. 先排序，讓後續能用大小關係做剪枝

先 sort(nums.begin(), nums.end())。

排序後同一個值會集中在一起，且越後面越大，這讓我可以做提早停止，也能讓 z 指標只往左移。

2. 固定第一個數 `nums[x]`，把目標變成 two-sum

用 x 從 0 跑到 n - 3，每次固定 nums[x] 當作三元組的第一個數。

我用 before 跳過重複的 nums[x]；若 nums[x] == before，就 continue。另外如果 nums[x] > 0 就直接 break。

3. 對每個 x，用 y 掃右邊，並讓 z 從最右邊往左縮

先把 z = n - 1 設在最右端
再用 y 從 x + 1 往右掃

對每個 y，一直嘗試用目前的 y 配上目前的 z：

若 nums[y] + nums[z] == -nums[x]，加入答案
若 nums[y] + nums[z] < -nums[x]，代表太小，直接 break 換下一個更大的 y
否則代表太大，z-- 往左縮小總和

4. 全部找完後，對 `ans` 排序並去除重複三元組

因為內層沒有完整處理 y、z 的重複值，所以最後用答案後處理去重。

先 sort(ans.begin(), ans.end())，再用 check 從後往前掃，重複就 erase。

5. 回傳去重後的 `ans`

最後回傳 ans，就是所有不重複的三元組。

⏱️ 複雜度

時間複雜度：大約 O(n^2)，另外 sort(ans) 是 O(m log m)，m 為找到的三元組數量。
空間複雜度：O(m)，ans 用來存放所有答案。

💻 程式碼實作

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        int before = INT_MAX;
        for (int x = 0; x < n - 2; x++) {
            if (nums[x] == before) {
                continue;
            }
            before = nums[x];
            if (nums[x] > 0) {
                break;
            }
            int z = n - 1;
            for (int y = x + 1; y < n; y++) {
                while (z > y) {
                    if (nums[y] + nums[z] == -nums[x]) {
                        ans.push_back({nums[x], nums[y], nums[z]});
                    } else if (nums[y] + nums[z] < -nums[x]) {
                        break;
                    }
                    z--;
                }
            }
        }

        sort(ans.begin(), ans.end()); // 去重複
        vector<int> check(3, INT_MAX);
        for (int i = ans.size() - 1; i >= 0; i--) {
            if (check != ans[i]) {
                check = ans[i];
            } else {
                ans.erase(ans.begin() + i);
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/3sum/