[数据结构与算法]LeetCode 15. 三数之和

15. 三数之和

题目描述

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

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

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

解题思路

思路一： 排序 + 双指针

本题的难点在于如何去除重复解。
为了解决这个问题， 我们可以将数组进行排序， 当nums[i] === nums[i - 1]时， 此时将nums[i]作为第一个数与nums[i - 1]作为第一个数得到的满足条件的三元组是一致的， 所以此时nums[i]我们就不再进行判断， 此时就可以避免出现重复解，当然对于第二个数、第三个数判断条件也是一样。

算法流程：

1. 对数组进行排序；
2. 遍历排序后数组：
   • 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数和等于 0，直接返回结果。
   • 对于重复元素：跳过，避免出现重复解
   • 令left = i + 1, right = nums.length - 1, 此时判断nums[i] + nums[left] + nums[right] 结果等于0即可； 当 left < right 时，执行循环：
     • 当和等于0，则加入结果集并执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 left 右移 right 左移，寻找新的解
     • 若和大于 0，说明 nums[right] 太大，right 左移
     • 若和小于 0，说明 nums[left] 太小，left 右移

实现代码如下：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let result = [], 
        len = nums.length,
        left, 
        right;
    // 先进行排序
    nums.sort((a, b) => a - b);
    for (let i = 0; i < len; i++) {
        let curr = nums[i];
        // 第一个数大于 0，后面的数都比它大，肯定不成立
        if (curr > 0) break;
        // 对第一个数去重
        if (i > 0 && curr === nums[i - 1]) continue;

        left = i + 1; 
        right = len - 1;
        while(left < right) {
            const sum = curr + nums[left] + nums[right];
            if (!sum) {
                result.push([curr , 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 if (sum > 0) {
                right--; 
            } 

        }
    }
    return result;
};

• 时间复杂度：$O(n^2)$，其中 n 是数组 nums 的长度。数组排序 $O(nlogn)$，遍历数组 $O(n)$，双指针遍历 $O(n)$，总体 $O(nlogn)+O(n)?O(n)$，即$O(n^2)$

• 空间复杂度：$O(logn)$

参考资料

排序 + 双指针，逐行解释 - 三数之和 - 力扣（LeetCode）