三数之和

题目

https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvpj16/

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i!= j、i!= k 且 j!= k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

实现

思路：排序加双指针，设定 i<j<k，当 i 固定时查询是否存在 nums[j],nums[k] 满足条件 边界：0<=i<j<k<=nums[length-1] 注意：三元组去重

复杂度分析

• 时间复杂度：排序 $O(n\log n)$+ 双层循环 $O(n^2)$
• 空间复杂度：$O(1)$

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 思路：双指针，设定i<j<k，当i固定时查询是否存在nums[j],nums[k]满足条件
// 边界：0<=i<j<k<=nums[length-1]
// 注意：三元组去重
var threeSum = function (nums) {
    const n = nums.length;
    const res = [];
    nums.sort((a, b) => a - b)
    for (let i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break; // 因为数组已排序，i>0时三数和不可能为0
        // 去重
        if (i > 0 && nums[i] == nums[i - 1]) continue;
 
        let j = i + 1, k = n - 1;
        while (j < k) {
            let sum = nums[i] + nums[j] + nums[k]
            if (sum == 0) {
                res.push([nums[i], nums[j], nums[k]]);
                // 去重
                while (j < k && nums[j] === nums[j + 1]) j++;
                while (j < k && nums[k] === nums[k - 1]) k--;
                j++;
                k--;
            } else if (sum < 0) j++
            else k--
        }
 
    }
    return res;
 
};