LeetCode | 三数之和

分类：双指针 / 数组 / 排序

题目#

给定一个整数数组 nums，找出所有和为 0 的三元组。

结果中不能包含重复的三元组。

示例：

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

讲解#

笔者的失败尝试#

一开始可以从两数之和的思路出发：固定第一个数 nums[first]，然后把问题变成在后面的数字里找两个数。

也就是：

1
nums[first] + nums[second] + nums[third] = 0

固定 nums[first] 后，就变成：

1
nums[second] + nums[third] = -nums[first]

这个思路本身是合理的，因为它确实把三数之和转成了两数之和的形式。

问题出在具体查找第三个数的写法：

1
target_third in nums[second + 1:]

这里的 nums[second + 1:] 不是在原列表上直接查找，而是先复制出一个新列表。切片复制需要 O(n)。

然后 target_third in 新列表 又是在列表里线性查找，也需要 O(n)。

所以这个方法整体接近：

1
外层 first        -> O(n)
2
内层 second       -> O(n)
3
切片和列表查找    -> O(n)
4
总时间复杂度      -> O(n^3)

虽然代码里用了 set 保存答案来去重，但它只是用来保存结果，不是用来做两数之和里的快速查找。所以这不是一个真正高效的哈希表解法。

这个方法在 LeetCode 上测试会超出时间限制。

基础思路#

暴力做法是枚举三个下标 i、j、k，检查 nums[i] + nums[j] + nums[k] 是否等于 0。这样有三层循环，时间复杂度是 O(n^3)。

这道题可以先排序，再用双指针。

排序之后，数组从小到大排列。我们先固定第一个数 nums[i]，然后在它右边找另外两个数。

此时问题变成：在 nums[i+1:] 里找两个数，让它们的和等于 -nums[i]

这就可以用双指针：

1
left  = i + 1
2
right = n - 1

如果三个数的和小于 0，说明当前和太小，需要让它变大，所以 left 往右移。

如果三个数的和大于 0，说明当前和太大，需要让它变小，所以 right 往左移。

如果刚好等于 0，就记录答案，然后两个指针都向中间移动。

这题还有一个关键点：去重。

固定第一个数时，如果 nums[i] == nums[i - 1]，说明这个第一个数之前已经用过，直接跳过。

找到一个答案之后，left 和 right 也要跳过相同的数字，否则会得到重复三元组。

1
left += 1
2
right -= 1
3
while left < right and nums[left] == nums[left - 1]:
4
    left += 1
5
while left < right and nums[right] == nums[right + 1]:
6
    right -= 1

剪枝#

第一个剪枝是：

1
if nums[i] > 0:
2
    break

数组已经排序，如果第一个数都大于 0，后面的数只会更大，不可能再凑出和为 0 的三元组。

笔者还尝试过另一个剪枝。固定 nums[i] 后，需要找两个数，让它们的和等于：

1
target = -nums[i]

第一版写法是先除以 2：

1
half = target / 2
2
if nums[left] > half or nums[right] < half:
3
    break

这个判断的意思是：

如果 nums[left] > half，说明当前最小的左边数已经太大了。因为 nums[right] >= nums[left]，所以两个数相加只会更大，不可能等于 target。
如果 nums[right] < half，说明当前最大的右边数也太小了。因为 nums[left] <= nums[right]，所以两个数相加只会更小，也不可能等于 target。

这个剪枝在数学上是成立的，但是 / 2 会引入浮点数计算，以及整数和浮点数之间的比较，开销更大。

后来把它改成了乘以 2 的版本：

1
target = -nums[i]
2
if nums[left] * 2 > target or nums[right] * 2 < target:
3
    break

这样可以避免浮点数，全部用整数比较。

但是加上这个剪枝以后，实际耗时还是增加了。原因是它需要在每次 while 循环里多做两次判断，而这个剪枝真正能提前结束循环的次数不够多，省下来的循环抵不过多出来的判断成本。

所以最终代码不加这个剪枝，只保留 nums[i] > 0 这个简单有效的剪枝。

复杂度#

暴力做法：
- 时间复杂度：O(n^3)
- 空间复杂度：O(1)
失败的方法（哈希表）：
- 时间复杂度：O(n^3)
- 空间复杂度：O(n)
排序 + 双指针：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)

失败的方法里有两层循环，里面的 nums[second + 1:] 和 in 查找又需要 O(n)，所以总时间复杂度接近 O(n^3)。ans 需要保存结果，切片也会临时创建新列表，所以空间复杂度按 O(n) 理解。

排序需要 O(n * log(n))，双指针部分是 O(n^2)，整体主要看 O(n^2)。

一些语法基础#

这道题里面有两个语法问题。

第一个是：

1
for i in range(n - 2):

这里不需要额外判断 n 有没有大于等于 3。

循环体会直接跳过，不会执行，也不会报错。

如果 n - 2 小于等于 0，比如 range(-1)、range(-2)，循环体会直接跳过，不会执行，也不会报错。

第二个是：

1
nums.sort()

sort() 是列表自己的方法，会直接修改原列表。

比如：

1
nums = [-1, 0, 1, 2, -1, -4]
2
nums.sort()

执行后，nums 自己会变成：

1
[-4, -1, -1, 0, 1, 2]

它和 sorted() 的区别是：

1
nums.sort()   -> 原地排序，修改 nums 本身，返回 None
2
sorted(nums)  -> 返回一个新的排序结果，不修改 nums 本身

在字母异位词分组里用的是 sorted(st)，因为那里要把字符串里的字符排序。字符串没有 sort() 方法，所以不能写 st.sort()。

代码#

失败的方法（哈希表）#

源码#

1
from typing import List
2

3

4
class Solution:
5
    def threeSum(self, nums: List[int]) -> List[List[int]]:
6
        length = len(nums)
7
        nums.sort()
8
        ans = set()
9

10
        for first in range(0, length):
11
            if nums[first] > 0:
12
                break
13
            target = 0 - nums[first]
14
            for second in range(first + 1, length):
15
                if nums[second] > target:
16
                    break
17
                target_third = target - nums[second]
18
                if target_third in nums[second + 1:]:
19
                    ans.add((nums[first], nums[second], target_third))
20

21
        return [list(item) for item in ans]

双指针#

源码#

1
from typing import List
2

3

4
class Solution:
5
    def threeSum(self, nums: List[int]) -> List[List[int]]:
6
        nums.sort()
7
        ans = []
8
        n = len(nums)
9

10
        for i in range(n - 2):
11
            if i > 0 and nums[i] == nums[i - 1]:
12
                continue
13
            if nums[i] > 0:
14
                break
15

16
            left = i + 1
17
            right = n - 1
18
            while left < right:
19
                total = nums[i] + nums[left] + nums[right]
20
                if total < 0:
21
                    left += 1
22
                elif total > 0:
23
                    right -= 1
24
                else:
25
                    ans.append([nums[i], nums[left], nums[right]])
26
                    left += 1
27
                    right -= 1
28
                    while left < right and nums[left] == nums[left - 1]:
29
                        left += 1
30
                    while left < right and nums[right] == nums[right + 1]:
31
                        right -= 1
32

33
        return ans

测试#

1
from src.python._015_Three_Sum import Solution
2

3

4
def normalize(ans):
5
    return sorted(sorted(x) for x in ans)
6

7

8
sol = Solution()
9

10
assert normalize(sol.threeSum([-1, 0, 1, 2, -1, -4])) == normalize([[-1, -1, 2], [-1, 0, 1]])
11
assert normalize(sol.threeSum([0, 1, 1])) == []
12
assert normalize(sol.threeSum([0, 0, 0])) == [[0, 0, 0]]
13
assert normalize(sol.threeSum([])) == []
14

15
print("PASS")

参考资料#

LeetCode 原题：https://leetcode.com/problems/3sum/
力扣官方题解：https://leetcode.cn/problems/3sum/solutions/284681/san-shu-zhi-he-by-leetcode-solution/

音乐

音乐

题目#

讲解#