What pattern does 3Sum primarily use?

3Sum leverages two-pointer scanning with invariant tracking after sorting the array, allowing systematic sum checks and duplicate management.

How do I avoid duplicate triplets in 3Sum?

Skip duplicate elements when fixing the first number and after finding valid triplets, move left and right pointers past identical values to maintain uniqueness.

Can 3Sum handle arrays with multiple zeros?

Yes, the algorithm naturally handles multiple zeros by skipping duplicates while scanning, ensuring only unique triplets like [0,0,0] are included once.

Why is sorting necessary in 3Sum?

Sorting ensures that the two-pointer scan works correctly, enabling deterministic pointer movements and simplifying duplicate detection to prevent repeated triplets.

What is the time and space complexity of 3Sum?

The overall time complexity is O(n^2) due to nested loops with two-pointer scanning, and space complexity is O(1) excluding the output list storing the triplets.

#15

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j 、 i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中…

数组双指针排序

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != 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
-10⁵ <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：排序 + 双指针

我们注意到，题目不要求我们按照顺序返回三元组，因此我们不妨先对数组进行排序，这样就可以方便地跳过重复的元素。

接下来，我们枚举三元组的第一个元素 $nums[i]$ ，其中 $0 \leq i \lt n - 2$ 。对于每个 $i$ ，我们可以通过维护两个指针 $j = i + 1$ 和 $k = n - 1$ ，从而找到满足 $nums[i] + nums[j] + nums[k] = 0$ 的 $j$ 和 $k$ 。在枚举的过程中，我们需要跳过重复的元素，以避免出现重复的三元组。

具体判断逻辑如下：

如果 $i \gt 0$ 并且 $nums[i] = nums[i - 1]$ ，则说明当前枚举的元素与上一个元素相同，我们可以直接跳过，因为不会产生新的结果。

如果 $nums[i] \gt 0$ ，则说明当前枚举的元素大于 $0$ ，则三数之和必然无法等于 $0$ ，结束枚举。

否则，我们令左指针 $j = i + 1$ ，右指针 $k = n - 1$ ，当 $j \lt k$ 时，执行循环，计算三数之和 $x = nums[i] + nums[j] + nums[k]$ ，并与 $0$ 比较：

如果 $x \lt 0$ ，则说明 $nums[j]$ 太小，我们需要将 $j$ 右移一位。
如果 $x \gt 0$ ，则说明 $nums[k]$ 太大，我们需要将 $k$ 左移一位。
否则，说明我们找到了一个合法的三元组，将其加入答案，并将 $j$ 右移一位，将 $k$ 左移一位，同时跳过所有重复的元素，继续寻找下一个合法的三元组。

枚举结束后，我们即可得到三元组的答案。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组的长度。

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

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = []
        for i in range(n - 2):
            if nums[i] > 0:
                break
            if i and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, n - 1
            while j < k:
                x = nums[i] + nums[j] + nums[k]
                if x < 0:
                    j += 1
                elif x > 0:
                    k -= 1
                else:
                    ans.append([nums[i], nums[j], nums[k]])
                    j, k = j + 1, k - 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you see how sorting simplifies duplicate management in two-pointer scanning?
question_mark
Can you explain why moving both pointers inward maintains the sum invariant?
question_mark
Will you handle cases with multiple zeros or repeated numbers correctly?

warning

常见陷阱

外企场景

error
Failing to skip duplicate fixed elements leads to repeated triplets in output.
error
Not advancing pointers past duplicate values after finding a triplet can cause repeated results.
error
Assuming unsorted arrays allow direct two-pointer scans without first sorting, breaking the invariant logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find all triplets that sum to a specific target value instead of zero, still avoiding duplicates.
arrow_right_alt
Return the count of unique triplets instead of the actual triplet arrays, focusing on optimization.
arrow_right_alt
Extend to 4Sum by fixing two elements and using two-pointer scanning for the remaining pair, managing duplicates carefully.

help

常见问题

外企场景

继续练习

#16 最接近的三数之和 #18 四数之和 #75 颜色分类