15. 3Sum

// 演算法 / Algorithm:
//   先排序，再固定第一個數 nums[i]，在其右側用雙指針找另外兩數使三數和為 0。
//   Sort first, then fix nums[i] and use two pointers on its right to find a pair summing to -nums[i].
//   排序讓我們可以跳過重複值來去重，整體 O(n^2)。
//   Sorting lets us skip duplicates; overall O(n^2).

#include <stdlib.h>  // 提供 malloc/free/qsort / provides malloc, free, qsort

// qsort 需要的比較函式：回傳負/零/正代表 a<b / a==b / a>b
// Comparator required by qsort: returns negative/zero/positive for a<b / a==b / a>b
static int cmp(const void *a, const void *b) {
    int x = *(const int *)a;  // 把 void* 轉回 int* 再解參考取值 / cast void* back to int* and dereference
    int y = *(const int *)b;  // 同上，取第二個值 / same for the second value
    // 不用 (x - y)，因為大數相減可能整數溢位 / avoid (x - y): subtraction can overflow for large ints
    if (x < y) return -1;     // x 較小排前面 / x goes first
    if (x > y) return 1;      // x 較大排後面 / x goes later
    return 0;                 // 相等 / equal
}

/**
 * 回傳值是 int**（指向多個 int* 的指標，即「陣列的陣列」）。
 * Return type is int** : a pointer to many int* rows, i.e. a 2D array.
 * returnSize       : 寫回三元組的數量 / number of triplets we produce
 * returnColumnSizes: 寫回每一列的長度（這裡每列都是 3）/ length of each row (always 3 here)
 */
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 先排序，雙指針法的前提 / sort first — the two-pointer method relies on it
    qsort(nums, numsSize, sizeof(int), cmp);

    int capacity = 16;  // 結果陣列初始容量，不夠時再加倍 / initial capacity, doubled when full
    // 申請存放「每個三元組指標」的空間 / allocate space for the row pointers
    int **res = (int **)malloc(sizeof(int *) * capacity);
    // 同步申請每列長度的陣列 / allocate the parallel array of row lengths
    *returnColumnSizes = (int *)malloc(sizeof(int) * capacity);
    int count = 0;      // 目前已找到的三元組數量 / how many triplets found so far

    // 固定第一個數 nums[i]；只需走到倒數第三個 / fix nums[i]; stop at the third-to-last
    for (int i = 0; i < numsSize - 2; i++) {
        // 剪枝：排序後若 nums[i] > 0，後面都更大，和不可能為 0 / prune: if smallest > 0, no zero sum possible
        if (nums[i] > 0) break;
        // 去重：i 與前一個值相同則跳過，避免重複開頭 / skip duplicate i to avoid repeated triplets
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1;          // 左指針從 i 右邊開始 / left pointer starts just right of i
        int right = numsSize - 1;  // 右指針從陣列尾端開始 / right pointer starts at the end

        while (left < right) {     // 兩指針未交錯時持續 / continue while pointers have not crossed
            // 用 int 相加可能溢位嗎？最大 3*10^5，遠小於 int 上限，安全 / sum fits in int (max ~3*10^5)
            int sum = nums[i] + nums[left] + nums[right];

            if (sum < 0) {
                left++;            // 和太小，需要更大的數 → 左指針右移 / too small, need larger → move left up
            } else if (sum > 0) {
                right--;           // 和太大，需要更小的數 → 右指針左移 / too big, need smaller → move right down
            } else {
                // 命中！容量不足就把陣列加倍 / hit! grow arrays if full
                if (count == capacity) {
                    capacity *= 2;
                    res = (int **)realloc(res, sizeof(int *) * capacity);
                    *returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * capacity);
                }
                // 為這一組三元組申請 3 個 int / allocate 3 ints for this triplet
                int *triplet = (int *)malloc(sizeof(int) * 3);
                triplet[0] = nums[i];      // 第一個數 / first number
                triplet[1] = nums[left];   // 第二個數 / second number
                triplet[2] = nums[right];  // 第三個數 / third number
                res[count] = triplet;              // 存入結果列 / store the row
                (*returnColumnSizes)[count] = 3;   // 這列長度為 3 / this row has length 3
                count++;                           // 計數加一 / increment count

                // 去重：跳過與當前相同的 left / skip duplicates of nums[left]
                while (left < right && nums[left] == nums[left + 1]) left++;
                // 去重：跳過與當前相同的 right / skip duplicates of nums[right]
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;   // 移到下一個不同的左值 / advance to next distinct left
                right--;  // 移到下一個不同的右值 / advance to next distinct right
            }
        }
    }

    *returnSize = count;  // 把三元組數量寫回給呼叫者 / report the count back to the caller
    return res;           // 回傳結果陣列 / return the 2D result
}

// 演算法 / 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
    }
};