#三数之和

/**
 * 找出数组中所有和为 0 的三元组
 * 使用排序 + 双指针算法，时间复杂度 O(n²)
 *
 * @param nums - 输入的整数数组
 * @returns 所有和为 0 的三元组数组，不包含重复的三元组
 *
 * @example
 * ```ts
 * threeSum([-1, 0, 1, 2, -1, -4]) // [[-1, -1, 2], [-1, 0, 1]]
 * threeSum([0, 0, 0]) // [[0, 0, 0]]
 * threeSum([0, 1, 1]) // []
 * ```
 */
export function threeSum(nums: number[]): number[][] {
    // 边界判断：如果数组长度小于 3，无法组成三元组，直接返回空数组
    if (nums.length < 3) {
        return [];
    }

    // 用于存储所有满足条件的三元组
    const res: number[][] = [];
    // 缓存数组长度，避免重复计算
    const len = nums.length;

    // 先对数组从小到大排序
    // 排序的好处：1. 可以使用双指针 2. 方便去重 3. 可以提前终止循环
    nums.sort((a, b) => a - b);

    // 外层循环：固定第一个数 nums[i]
    // 注意：i 只需要遍历到 len - 2，因为后面至少要留两个位置给 L 和 R
    for (let i = 0; i < len; i++) {
        // 优化：如果当前数字大于 0，由于数组已排序，后面的数字都 > 0
        // 三个正数的和不可能为 0，所以直接退出循环
        if (nums[i] > 0) break;

        // 去重：如果当前数字与前一个数字相同，跳过
        // 避免产生重复的三元组，例如 [-1, -1, 2] 只需要找一次
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        // 定义左右双指针
        // L 指向 i 的下一个位置（左边界）
        let L = i + 1;
        // R 指向数组的最后一个位置（右边界）
        let R = len - 1;

        // 双指针向中间收缩，寻找满足条件的三元组
        while (L < R) {
            // 计算三个数的和
            const sum = nums[i] + nums[L] + nums[R];

            // 情况 1：和为 0，找到一个满足条件的三元组
            if (sum === 0) {
                // 将这个三元组加入结果数组
                res.push([nums[i], nums[L], nums[R]]);

                // 去重：跳过所有与当前 L 相同的元素
                // 例如：[-2, 0, 0, 2, 2]，找到 [-2, 0, 2] 后，跳过重复的 0 和 2
                while (L < R && nums[L] === nums[L + 1]) L++;
                // 去重：跳过所有与当前 R 相同的元素
                while (L < R && nums[R] === nums[R - 1]) R--;

                // 同时移动双指针，继续寻找下一组解
                L++;
                R--;
            }
            // 情况 2：和小于 0，说明数值太小，需要增大
            // 由于数组已排序，移动左指针可以增大和
            else if (sum < 0) {
                L++;
            }
            // 情况 3：和大于 0，说明数值太大，需要减小
            // 移动右指针可以减小和
            else {
                R--;
            }
        }
    }

    // 返回所有满足条件的三元组
    return res;
}