题目描述

[EN | CN]

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

注意:

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

示例:

1
2
3
4
5
6
7
给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解法 1:暴力

最直接(暴力)的做法就是遍历所有的 3 数组合。

如果数组长度为 $n$,那么

  • 时间复杂度是 $O(n^3)$,不可接受;
  • 空间复杂度为 $O(1)$。

代码略。

解法 2:哈希 + 两指针

换个思路,将该数组存入一个哈希表,然后再算所有的 2 数组合的和的相反数是否已经存在哈希表内,这样的话实现起来比较麻烦,包括扫描一遍($O(n)$)、两两组合($O(n^2)$)、去重($O(n)$),还要排除相反数跟两位数组合的其中一个被选中了两次的情况,时间复杂度至少也是 $O(n^2)$,实现起来比较麻烦。

如果数组长度为 $n$,那么

  • 时间复杂度是 $O(n^2)$;
  • 空间复杂度为 $O(n)$。

代码略。

解法 3:排序 + 三指针

我们换一种思路,能不能把「去重」这一步去掉?这个时候排序算法就能排上用场了。在这题中,要算 3 个数的和,哪怕我们固定第三个数为一个集合($O(n)$),那计算剩下的两个数最少也需要 $O(n^2)$,而众所周知,排序算法的时间复杂度是 $O(n \log n)$,可以无缝接入。

如果照我们上面说的求任意两数之和然后去集合中找是否存在其相反数,因为多方都在变化(即 2 数的组合、第 3 个数的集合),所以比较才这么麻烦。所以我们可以换一个思路,通过排序来增加「确定性」。具体来说,我们可以每次都固定第一个数(记为 A),然后在剩下的数中找两个数(记为 BC)能够加起来等于 A 的相反数,此时排序的性质就很有用。大致的步骤如下:

  1. A 从索引 0 开始;
  2. BA 的右侧开始,C 从数组的末尾开始;
  3. 计算 ABC 的和:
    • 如果 A + B + C < 0,那么 B 往右移动;
    • 如果 A + B + C > 0,那么 C 往左移动;
    • 如果 A + B = C,那么返回当前组合,然后 B 往右移动,且 C 往左移动;
  4. 重复第 3 步,持续往中间「夹」,直到 BC 相遇;
  5. A 往右走一步,重复第 2-4 步。

注意,遇到重复的数字是可以跳过的(包括 ABC),因为已经挑过了有它的组合。

通过这种方式,我们选好的结果都是 唯一的、不重复的,不需要额外进行去重等操作

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n^2)$,躲不过躲不过;
  • 空间复杂度为 $O(1)$,不需要额外空间。

实现与结果如下:

 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
26
27
28
29
30
31
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        rets = []

        for a in range(len(nums) - 2):

            if a > 0 and nums[a] == nums[a - 1]:
                continue

            b = a + 1
            c = len(nums) - 1

            while b < c:
                sum_ = nums[a] + nums[b] + nums[c]
                if sum_ < 0:
                    b += 1
                elif sum_ > 0:
                    c -= 1
                else:
                    rets.append([nums[a], nums[b], nums[c]])

                    while b < c and nums[b] == nums[b + 1]:
                        b += 1
                    while b < c and nums[b] == nums[b + 1]:
                        c -= 1

                    b += 1
                    c -= 1

        return rets
  • 执行用时:856 ms,在所有 Python3 提交中击败了 82.20% 的用户。
  • 内存消耗:16.4 MB,在所有 Python3 提交中击败了 10.98% 的用户。