// 演算法 / Algorithm:
//   排序後固定 nums[i]，在右側用雙指針找另外兩數使三數和為 0；
//   Sort, fix nums[i], then two-pointer search on its right for a pair summing to -nums[i];
//   靠跳過相同值來去除重複三元組，整體 O(n^2)。
//   Skip equal values to drop duplicate triplets; overall O(n^2).

#include <vector>     // std::vector 動態陣列 / dynamic array
#include <algorithm>  // std::sort 排序 / sorting

class Solution {
public:
    // 回傳「向量的向量」，每個內層 vector 是一組三元組 / returns a vector of triplets
    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());  // 由小到大排序 / sort ascending
        std::vector<std::vector<int>> res;    // 存放答案 / holds the answer
        int n = nums.size();                  // 陣列長度 / array length

        // 固定第一個數，i 只需到倒數第三個 / fix the first number, i stops at n-2
        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] > 0) break;                       // 剪枝：最小值已 >0 / prune: smallest already > 0
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重 i / skip duplicate i

            int left = i + 1;   // 左指針 / left pointer
            int right = n - 1;  // 右指針 / right pointer

            while (left < right) {
                // 用 long 相加避免理論溢位（雖然這裡 int 也夠）/ use long to be safe against overflow
                long sum = (long)nums[i] + nums[left] + nums[right];

                if (sum < 0) {
                    ++left;          // 和太小 → 左指針右移 / too small → move left right
                } else if (sum > 0) {
                    --right;         // 和太大 → 右指針左移 / too big → move right left
                } else {
                    // 命中！emplace_back 直接在尾端就地建構這個三元組 / hit! build the triplet in place at the end
                    res.push_back({nums[i], nums[left], nums[right]});

                    // 跳過重複的 left 與 right / skip duplicate left and right values
                    while (left < right && nums[left] == nums[left + 1]) ++left;
                    while (left < right && nums[right] == nums[right - 1]) --right;

                    ++left;   // 前進到下一個不同左值 / move to next distinct left
                    --right;  // 前進到下一個不同右值 / move to next distinct right
                }
            }
        }
        return res;  // 回傳所有三元組 / return all triplets
    }
};