---
title: "20240327-LeetCode-15.三数之和"
source: https://www.iowill.com/blog/2024/09/leetcode-15-3sum/
date: 2024-09-20
updated: 2026-10-14
tags: [LeetCode, 双指针, 排序, 数组]
categories: [算法与数据结构]
---

# 20240327-LeetCode-15.三数之和

## 题目描述

给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请

你返回所有和为 `0` 且不重复的三元组。

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

**示例 1：**

```plaintext
输入：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：**

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

**示例 3：**

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

**提示：**

-   `3 <= nums.length <= 3000`
-   `-105 <= nums[i] <= 105`

## 解题

总体思路是参考**1.两数之和**，三数之和的话，只需选定一个数假定为`A`，那么就转化为两数之和问题了，要求解的另外两个数假定为`B`和`C`，满足`B+C=-A`，即两数之和问题。

```cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret; // 保存结果三元组
        int len = nums.size();
        sort(nums.begin(), nums.end());
        if (nums[0] > 0 || nums[len-1] < 0) {
            return ret; // 过滤一下不可能凑出三数之和条件的情况
        }
        for (int i = 0; i < len; ++i) { // nums[i]即为选定的第一个数，那么剩下满足条件的两个数就是两数之和问题
            if (i > 0 && nums[i] == nums[i-1]) {
                continue; // 如果和上一轮循环判断的数相同则没必要再判断一次了，跳过直到遇到不同的数
            }
            int li = i + 1, ri = len - 1; // 定义双指针，左指针从左往右，右指针从右往左
            int target = -nums[i]; // nums[i]是选定的数，那么剩下两数之和则为-nums[i]
            while (li < ri) { // 左指针必须在右指针左边
                while (nums[li] + nums[ri] < target && li < ri) ++li; // 如果此时左右指针指向的两数之和比目标和小，说明应该增大其中某个数，即左指针右移
                if (li >= ri) break; // 当左右指针相遇了，说明不存在满足两数之和为target的两个数
                while (nums[li] + nums[ri] > target && li < ri) --ri; // 如果此时左右指针指向的两数之和比目标和大，说明应该减小其中某个数，即右指针左移
                if (li >= ri) break; // 当左右指针相遇了，说明不存在满足两数之和为target的两个数
                if (nums[li] + nums[ri] == target) { // 当找到两个数满足两数之和条件时
                    ret.push_back({nums[i], nums[li], nums[ri]}); // 与第一选定数合并即为满足三数之和的三元组，加入结果集合中
                    while (nums[li++] == nums[li] && li < ri); // 如果和上一轮循环判断的数相同则没必要再判断一次了，跳过直到遇到不同的数
                    if (li >= ri) break; // 当左右指针相遇了，说明所有可能的二元组都遍历完了
                    while (nums[ri--] == nums[ri] && li < ri); // 如果和上一轮循环判断的数相同则没必要再判断一次了，跳过直到遇到不同的数
                    if (li >= ri) break; // 当左右指针相遇了，说明所有可能的二元组都遍历完了
                }
            }
        }
        
        return ret;
    }
};
```