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