【LeetCode】15. 三数之和(中等)——代码随想录算法训练营Day07

发布时间:2024年01月16日

题目链接:15. 三数之和

题目描述

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

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

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]

输出:[[-1,-1,2],[-1,0,1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]

输出:[]

解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]

输出:[[0,0,0]]

解释:唯一可能的三元组和为 0 。

提示:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

文章讲解:代码随想录

视频讲解:梦破碎的地方!| LeetCode:15.三数之和_哔哩哔哩_bilibili

题解1:哈希表

思路:类似于1. 两数之和454. 四数相加 II,本题看到题目首先想到的方法是哈希表。要寻找三元组 (a, b, c),两层 for 循环可以确定 a 和 b 的值,用哈希表存储 b,符合条件的 c 即为 0 - a - b。

本题要求三元组中的元素不能重复,去重就成了一个难点。去重的过程不好处理,有很多小细节。首先要对数组进行排序,才方便后续的去重。(以去重后的数组为 [-3, -3, -2, -2, -2, 0, 0, 0, 1, 1, 1, 2, 2, 3, 5, 6]为例)

  • 对 a 去重:首先 a 一定是负数或0,如果 a 是正数,则本次遍历没有符合的三元组。第1层循环即锁定 a,寻找符合条件的 b 和 c。以 a 为 -3 为例,当前 a 为第1个-3时,找到符合条件的三元组 (-3, -3, 6)、(-3, -2, 5) 和 (-3, 1, 2),下次遍历时 a 是第2个-3,找到的三元组为 (-3, -2, 5) 和 (-3, 1, 2), 已经在上次遍历出现过了。因此,如果下轮遍历的 a 和本轮遍历的 a 相同,就应该跳过下次遍历(如果跳过本次遍历,就漏了 (-3, -3, 6) 的情况)。
  • 对 b 去重:以当前锁定 a 为 -2 寻找符合条件的 b 和 c 为例,对 a 去重后,当前遍历的数组序列为 [-2, 1, 1, 1, 2, 2, 3, 5, 6],符合条件的三元组为 (-2, 0, 2) 和 (-2, 1, 1)。对 b 去重,考虑到有 (-2, 1, 1) 这种情况,因此当有连续的3个b都相同时,应该跳过第3个 b。
  • 对 c 去重:锁定 a,寻找符合条件的 b 和 c,构造哈希表存储 b,根据当前的 a 和哈希表中的 b 寻找符合条件的 c。如当前 a 为 -2,哈希表中已经存储了元素 0、1 为 b,寻找符合条件的 c,即1和2。但后面的1和2有多个,需要对 c 进行去重。对 c 去重,可以在找1个匹配的? c?时,在哈希表中删掉对应的 b,下一个元素为相同的 c 时,就不会再得出重复的三元组了。

综上分析,哈希表结构适合使用集合,即 Set,Set 中重复的元素只会出现1次,当重复插入 b 时,也只会留下一个 b,符合我们的期望。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const res = [];
    const map = new Map();
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 2; i++) {
        // 排序之后如果第一个元素已经大于零,那么不可能凑成三元组
        if (nums[i] > 0) {
            break;
        }
        // 三元组元素 a 去重
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        const set = new Set(); // 用来存储 b
        for (let j = i + 1; j < nums.length; j++) {
            // 三元组元素去重 b
            if (j > i + 2 && nums[j] === nums[j - 1] && nums[j - 1] === nums[j - 2]) {
                continue;
            }
            // nums[i] 为 a,nums[j] 为 c
            let b = 0 - nums[i] - nums[j]; // 目标 b
            if (set.has(b)) {
                res.push([nums[i], b, nums[j]]);
                set.delete(b); // 三元组元素去重 c
            } else {
                set.add(nums[j]); // 将当前 c 作为新的 b 加入到哈希表中
            }
        }
    }
    return res;
};

分析:两层 for 循环,额外使用一个 Set 作为哈希表,时间复杂度为 O(n2),空间复杂度为 O(n)。

题解2:双指针

思路:我们要在数组中寻找符合条件的三元组 (a, b, c),可以将 a 固定,left 作为 b,right 作为 c,使用双指针法来求解。计算 a + b + c 的结果,如果大于0,就让右指针向左移动;如果小于 0,就让左指针向右移动。如果等于0,记录进结果数组,左右指针同时向中移动。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const res = [];
    nums.sort((a, b) => a - b);
    // 寻找结果 (a, b, c),i 为 a,left 为 b,right 为 c
    for (let i = 0; i < nums.length - 2; i++) {
        // 如果 a > 0 了,说明后面不会再找出符合条件的三元组了
        if (nums[i] > 0) {
            break;
        }
        // 对 a 去重
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            // 对 b 去重
            if (left > i + 1 && nums[left] === nums[left - 1]) {
                left++;
                continue;
            }
            // 对 c 去重
            if (right < nums.length - 1 && nums[right] === nums[right + 1]) {
                right--;
                continue;
            }
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                res.push([nums[i], nums[left++], nums[right--]]);
            } else if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }
    return res;
};

分析:时间复杂度为 O(n2),空间复杂度为 O(1)。

收获

更深一步理解了哈希表和双指针法的使用,在处理去重的细节的过程中进一步提高编码能力。

文章来源:https://blog.csdn.net/m0_57521762/article/details/135626798
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。