刷题笔记(6):力扣-15.三数之和

本题来自 leetcode 题库第 15 题:15.三数之和。题目要求在给定数组中找到所有和为 0 的三元组,且不可重复,难度中等。

题目描述

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

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

  • 示例 1:
    输入:nums = [-1,0,1,2,-1,-4]
    输出:[[-1,-1,2],[-1,0,1]]

  • 示例 2:
    输入:nums = []
    输出:[]

  • 示例 3:
    输入:nums = [0]
    输出:[]

  • 提示:
    0 <= nums.length <= 3000
    \(-10^5\) <= nums[i] <= \(10^5\)

题解

这道题最直接的思路就是 3 层循环暴力求解,然后在所有结果里去重。时间复杂度为 \(O(n^3)\),一般来说是非常高的的复杂度了,在处理较大的数据量时效率较低。并且在去重的时候要注意,数组 [1,2,3][2,1,3] 是被认为重复的。所以判断的时候要求两者的元素互相都在对方之中,用数学的表达来讲就很好理解:集合 \(A=B\),当且仅当 \(A\subset B\)\(B \subset A\)。但若两个数组是有序的,则只需判断对应的位置相同即可。同时又因为数组里 3 个元素的和都是 0,那么只要任意两位对应相同就可判断这两个数组等价,降低了去重的复杂度。

从有序数组去重比较方便和题目 167.两数之和 II - 输入有序数组 中的双指针受到启发,如果我们先将输入的数组排序,再来寻找和为 0 的三元组是不是更方便呢。事实上是这样的。

首先将输入数组 nums 排序,然后遍历该有序数组。对于每个 nums[i],在 nums[i + 1] 到数组末尾中寻找两个数和为 -nums[i],则这三个数就构成一个和为 0 的三元组。寻找两个数和为 -nums[i] 的问题类似 167.两数之和 II - 输入有序数组,不过要注意这里要找到所有和为 -nums[i] 的一对数。如此就能确保要找的三元组“不漏“。除此之外,还要做到“不重”。首先在遍历过程中对于相同的元素,我们只考虑第一个即可。其次我们在寻找后面两个数时,需要判断和前一个三元组是否重复。为什么只判断和前一个是否重复即可?原因同样在于数组是有序的,而我们的三元组也是有序的。具体地代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
nums.sort((a, b) => a - b)
const res = []
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
const a = nums[i]
let l = i + 1, r = nums.length - 1
while (l < r) {
const b = nums[l]
const c = nums[r]
if (b + c < -a) l++
else if (b + c > -a) r--
else {
if (res.length < 1 || b !== res[res.length - 1][1] || c !== res[res.length - 1][2])
res.push([a, b, c])
l++, r--
}
}
}
return res
};

注意代码中关于去重的细节较多,以及双指针的移动需要注意避免陷入死循环。至于为何能够做到“不重不漏”,上面的解释只是直观上的解释,其实需要更严谨的说明和思考,请读者注意。

该算法的排序的时间复杂度为 \(O(\log N)\),后面循环的复杂度为 \(O(N^2)\),所以时间复杂度为 \(O(N^2)\)。空间复杂度主要为排序时需要用到的 \(O(\log N)\)

总结与思考

这题的解法思路上看起来并不复杂,尤其是做过两数之和的题之后,但实际实现时需要注意的细节很多,主要在于要避免“不重不漏”,以及双指针的移动问题。

需要注意 JavaScript 中数组排序函数 nums.sort() 默认是按字符编码排序,这就意味着 112, 2, 3000 会被视为正确的排序。需要对数字数组进行升序排列,需要使用 nums.sort((a, b) => a - b)。该方法直接修改原数组,且返回原数组。