15. 三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

题解

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums = nums.sort((a, b) => a - b)
    let i = 0, j = 1
    let arr = []
    while (i <= nums.length - 3) {
        if (nums[i] <= 0 && nums[i] != nums[i - 1]) {
            j = i + 1
            let k = nums.length - 1
            while (j < k) {
                let a = nums[i] + nums[j] + nums[k]
                if (a == 0) {
                    arr.push([nums[i], nums[j], nums[k]])
                    j++
                    k--
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--
                    }
                }
                if (a > 0) {
                    k--
                }
                if (a < 0) {
                    j++
                }
            }
        }
        i++
    }
    return arr
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注