三数之和

[lzxjack]

No description provided.

[dossweet]

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例代码

这是一道经典的双指针题！

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
   const res = [], len = nums.length;
    nums.sort((a, b) => a - b);
    for (let i = 0; i < len - 2; i++){
        if (nums[i] > 0){
            return res;
        }
        if (nums[i] === nums[i - 1]){
            continue;
        }
        let left = i + 1;
        let right = len - 1;
        while (left < right){
            let sum = nums[i] + nums[left] + nums[right];

            if (sum > 0){
                right--;
            }else if (sum < 0){
                left++;
            }else{
                res.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--;
                }
                // 经过上述两个while，去重了相同的元素，但我们需要从下一个元素开始
                left++;
                right--;
            }
        }
    }
    return res;
};