15_三数之和

;(function(){
    /**
     * 15. 三数之和
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     * 注意：答案中不可以包含重复的三元组。
     * 
     * 输入：nums = [-1,0,1,2,-1,-4]
     * 输出：[[-1,-1,2],[-1,0,1]]
     * 
     * 输入：nums = []
     * 输出：[]
     * 
     * 输入：nums = [0]
     * 输出：[]
     * 
     */

    function threeSum(nums: number[]): number[][] {
        // 方法一：暴力循环 --- 超出时间限制
        // let set = new Set();
        // let res: number[][] = [];
        // for (let i = 0; i < nums.length; i++) {
        //     // a
        //     for (let j = i + 1; j < nums.length; j++) {
        //         // b
        //         for (let k = j + 1; k < nums.length; k++) {
        //             // c
        //             if (nums[i] + nums[j] + nums[k] === 0) {
        //                 let sortArr = [nums[i], nums[j], nums[k]].sort((a: number, b: number) => a - b);
        //                 let sortArrStr = sortArr.join('-')
        //                 if (!set.has(sortArrStr)) {
        //                     res.push(sortArr)
        //                     set.add(sortArrStr)
        //                 }
        //             }
        //         }
        //     }
        // }
        // return res

        // 方法二：
        // 1. 排序；2. 双指针
        let ans: number[][] = []
        const len = nums.length;
        if (nums === null || len < 3) return ans
        // 排序
        nums.sort((a: number, b: number) => a - b)
        for (let i = 0; i < len; i++) {
            // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if (nums[i] > 0) break;
            // 去重
            if (i > 0 && nums[i] === nums[i-1]) continue;
            let L = i + 1;
            let R = len - 1;
            while (L < R) {
                const sum = nums[i] + nums[L] + nums[R]
                if (sum === 0) {
                    ans.push([nums[i], nums[L], nums[R]])
                    // 去重
                    while(L < R && nums[L] === nums[L+1]) L++;
                    while(L < R && nums[R] === nums[R-1]) R--;
                    L++;
                    R--;
                } else if (sum < 0) {
                    L++
                } else if (sum > 0) {
                    R--
                }
            }
        }
        return ans

    };

    console.log(threeSum([-1,0,1,2,-1,-4]))

})()