[!info] related notes 双指针 两数之和2

三数之和

分析

关键在与想到 三数之和 = 0 就是 num1 + num2 = -num3 然后遍历 num3 转换成 两数之和2

function threeSum(nums: number[]): number[][] {
    const sortedNums = nums.sort((a, b) => a - b);
    
    // 优化： 当最小的数大于 0，肯定不存在三数和为 0
    if (nums[0] > 0) return [];

    const len = nums.length;
    let ans = [];
    for (let i = 0; i < len - 2; i++) {
    
	    // 关键： 去重
        if (i > 0 && nums[i] === nums[i-1]) continue;
        let left = i + 1, right = len - 1, target = -nums[i];
        while (left < right) {
            let sum = nums[left] + nums[right];
            if (sum === target) {
                ans.push([nums[i], nums[left], nums[right]]);

				// 关键： 要对相同的元素进行去重
                while( left < right && nums[left] === nums[left+1]) left++;
                while (left < right && nums[right] === nums[right-1]) right--;
            }
            sum > target ? right -- : left ++;
        }
        
    }
    return ans;
};