代码随想录

# 15. 三数之和

力扣题目链接 (opens new window)

# 题目描述

给你一个整数数组 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]。
1
2
3
4
5
6
7

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0。
1
2
3

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0。
1
2
3

提示：

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

# 思路

最直观的想法是什么？

三层 for 循环枚举三个数，判断它们的和是否为 0。但这种写法的时间复杂度是 O(n³)，当 n = 3000 时肯定会超时，而且还要额外处理重复三元组。

能不能先固定一个数，再快速找到另外两个数？

很多录友做过1. 两数之和，会马上想到哈希表。哈希法确实可以把时间复杂度降到 O(n²)，但本题还要求结果不能重复，哈希法的去重细节比较多，面试时很容易写出 bug。

本题更适合排序 + 双指针。

# 排序之后固定一个数

先将数组从小到大排序。然后遍历数组，固定 nums[i] 作为三元组中的第一个数 a，再在 i 后面的区间里寻找两个数 b 和 c：

a = nums[i]
b = nums[left]
c = nums[right]
1
2
3

其中：

  • left = i + 1
  • right = nums.size() - 1

为什么排序之后就可以用双指针？

因为此时 nums[left] 和 nums[right] 的变化是有方向的。计算：

sum = nums[i] + nums[left] + nums[right]
1
  • 如果 sum > 0，说明三数之和大了，right 向左移动，让和变小
  • 如果 sum < 0，说明三数之和小了，left 向右移动，让和变大
  • 如果 sum == 0，记录三元组，然后左右指针同时向中间收缩

这样，固定一个 i 之后，left 和 right 只会各自单向移动，寻找另外两个数的时间复杂度是 O(n)。外层再遍历一次 i，总时间复杂度就是 O(n²)。

# 剪枝

数组已经排好序，如果 nums[i] > 0，那么 nums[i] 以及它右边的数都大于 0，三个数相加不可能等于 0，可以直接结束遍历。

if (nums[i] > 0) {
    break;
}
1
2
3

# 去重

这道题真正容易写错的地方不是双指针，而是去重。

去重的是三元组，三元组内部的元素可以相同。

例如 [-1,-1,2] 和 [0,0,0] 都是合法答案，所以不能看到相邻元素相同就直接跳过。

# 对第一个数 a 去重

如果当前的 nums[i] 和上一次固定的数相同，那么这一轮找到的三元组一定已经出现过，直接跳过：

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}
1
2
3

注意，不能写成 nums[i] == nums[i + 1]。否则在 [-1,-1,2] 中，第一个 -1 会被跳过，这个合法答案也就丢了。

# 对第二、第三个数 b、c 去重

当 sum == 0，先记录当前三元组，再跳过 left 和 right 两侧相同的数：

while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
1
2

为什么要先收集答案再去重？

如果提前跳过重复数字，[0,0,0] 可能还没被记录，指针就已经相遇了。先收集，再去重，这一点很重要。

# 模拟过程

以 nums = [-1,0,1,2,-1,-4] 为例。

首先对数组排序，得到 [-4,-1,-1,0,1,2]。固定 i = 0，同时让 left 指向 i + 1，right 指向数组末尾。

此时 -4 + (-1) + 2 = -3 < 0，三数之和小了，需要让 left 向右移动，尝试找到更大的数。

当 i = 0 时，left 不断向右移动，直到与 right 相遇，这一轮没有找到答案。

接着令 i = 1，固定 a = -1。此时 left = 2、right = 5，三数之和为 -1 + (-1) + 2 = 0，记录第一个三元组 [-1,-1,2]。

找到答案后，先跳过 left、right 两侧的重复元素，再让两个指针同时向中间收缩。

此时 left = 3、right = 4，三数之和为 -1 + 0 + 1 = 0，记录第二个三元组 [-1,0,1]。

随后 i 移动到下标 2。由于 nums[2] 与上一次固定的 nums[1] 都是 -1，继续搜索只会得到重复三元组，所以跳过这一轮。

当 i = 3，固定 a = 0，left = 4、right = 5。此时 0 + 1 + 2 = 3 > 0，三数之和大了，right 向左移动。移动后 left 与 right 相遇，搜索结束。

最终得到：

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

# 解题代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            // 排序后第一个数已经大于0，后面不可能凑出和为0的三元组
            if (nums[i] > 0) {
                break;
            }

            // 对三元组中的第一个数去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum > 0) {
                    right--; // 和太大，让较大的数变小
                } else if (sum < 0) {
                    left++; // 和太小，让较小的数变大
                } else {
                    result.push_back({nums[i], nums[left], nums[right]});

                    // 先记录答案，再对第二、第三个数去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++;
                    right--;
                }
            }
        }

        return result;
    }
};
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
32
33
34
35
36
37
38
39
40
41
42
43

# 复杂度分析

  • 时间复杂度：O(n²)。排序需要 O(n log n)，外层遍历与内层双指针共需要 O(n²)。
  • 空间复杂度：O(log n)。主要是排序使用的栈空间，不计算返回结果所占空间。

# 其他语言

# Python3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []

        for i in range(len(nums)):
            if nums[i] > 0:
                break

            if i > 0 and nums[i] == nums[i - 1]:  # 对第一个数去重
                continue

            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total > 0:
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    result.append([nums[i], nums[left], nums[right]])

                    # 先记录答案，再对第二、第三个数去重
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1

        return result
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
32
33

# Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }

            if (i > 0 && nums[i] == nums[i - 1]) { // 对第一个数去重
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 先记录答案，再对第二、第三个数去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++;
                    right--;
                }
            }
        }

        return result;
    }
}
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
32
33
34
35
36
37
38
39
40

# Go

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := make([][]int, 0)

    for i := 0; i < len(nums); i++ {
        if nums[i] > 0 {
            break
        }

        if i > 0 && nums[i] == nums[i-1] { // 对第一个数去重
            continue
        }

        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]

            if sum > 0 {
                right--
            } else if sum < 0 {
                left++
            } else {
                result = append(result, []int{nums[i], nums[left], nums[right]})

                // 先记录答案，再对第二、第三个数去重
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }

                left++
                right--
            }
        }
    }

    return result
}
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
32
33
34
35
36
37
38
39
40

# JS

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            break;
        }

        if (i > 0 && nums[i] === nums[i - 1]) { // 对第一个数去重
            continue;
        }

        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];

            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                result.push([nums[i], nums[left], nums[right]]);

                // 先记录答案，再对第二、第三个数去重
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;

                left++;
                right--;
            }
        }
    }

    return result;
};
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
32
33
34
35
36
37
38

# 与代码随想录联系

我在代码随想录的三数之和中详细对比了哈希法和双指针法，也专门分析了 a、b、c 三个数的去重逻辑。

本题虽然收录在哈希表章节，但更推荐使用双指针法。它把暴力解法的 O(n³) 降到了 O(n²)，同时也比哈希法更容易处理重复结果。

和本题相关的题目：

上次更新：: 7/23/2026, 8:59:54 PM

评论

验证登录状态...