一、题目要求

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

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

二、题目思路

解法：排序 + 双指针

1.先对数组排序，便于去重和双指针移动；

2.固定一个数 nums[i]，然后在 i 右侧使用双指针寻找两数之和等于 -nums[i]

3.跳过重复元素，保证结果不重复

三、代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    //边界控制（数组长度小于3直接返回空值）
    if(nums.length < 3) return[];
    //排序（升序）
    nums.sort((a,b) => a-b);

    let result = [];
    const n = nums.length;

    for(let i = 0; i < n-2; i++){
        // 优化：如果当前最小的数都大于 0，三数之和不可能为 0，直接终止循环
        if (nums[i] > 0) break;

        // 跳过重复的 i，避免产生重复的三元组
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1;
        let right = n - 1;

        while(left < right){
            const sum = nums[i] + nums[left] + nums[right];

            if(sum == 0){
                // 找到一个合法三元组
                result.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--;
                }

                // 继续向内收缩
                left++;
                right--;
            }else if(sum < 0 ){
                // 和太小，左指针右移增大和
                left++;
            }else{
                //和太大，右指针左移减小和
                right--;
            }
        }
    }
    return result;
};

四、总结

该算法时间复杂度为O(n²)。