算法题解：三数之和与四数之和

讲解 LeetCode 中“三数之和”与“四数之和”问题的 C++ 解法。核心思路为排序后使用双指针技术。对于三数之和，固定一个数，在剩余区间内寻找两数之和；对于四数之和，固定两个数，在剩余区间内利用三数之和逻辑。重点在于去重处理（跳过重复元素）及边界条件判断。时间复杂度为 O(n^2)，空间复杂度为 O(log n)。

城市逃兵发布于 2026/3/28更新于 2026/4/176 浏览

在这里插入图片描述

1. 三数之和

在这里插入图片描述

LeetCode 题目链接

1.1 题目说明

给定一个整数数组 nums，判断数组中是否存在三个元素 nums[i], nums[j], nums[k]，使得它们的和为 0，返回所有符合条件且不重复的三元组。要求：

三元组 [nums[i], nums[j], nums[k]] 满足 i != j != k，同时 nums[i] + nums[j] + nums[k] == 0。
输出结果中不包含重复的三元组。

示例 1

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释：不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。

示例 2

输入：nums = [0, 1, 1] 输出：[]

示例 3

输入：nums = [0, 0, 0] 输出：[[0, 0, 0]]

1.2 题目分析

题目要求 nums[i] + nums[j] + nums[k] == 0。需要在数组中找到对应的三个数。

解法一： 暴力枚举法：将所有的可能性都表示出来，然后利用 set 进行去重操作。 解法二： 使用排序 + 双指针就能进行解决。

推荐选择第二种方法，因为效率高。

思路： 我们将排序好的数组的第一个数字进行固定操作，然后从 1 到 n-1 这个下标范围寻找满足两数之和为 0 条件的数字。在该区间内利用双指针进行查找。

总结：

先排序。
固定一个数 a（我们固定的数小于等于 0 就行了，不需要去固定大于 0 的。如果固定的是大于 0 的数字的话我们是不能在这个数后面的区间之内找到负数的）。当 a 大于 0 之后我们就不要进行考虑统计了。
在该数后面的区间内利用'双指针算法'，快速找到两个的和等于 -a 就行了。

处理细节问题：

去重：不借助 set 进行去重的操作。找到一种结果之后，left 和 right 要跳过重复元素。当使用完一次双指针算法之后，i 也需要跳过重复元素避免越界（如果数组中全是 0 的话，跳过重复元素，可能会存在越界的情况）。这个条件就会保证不越界了。

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; // 用 ret 来记录我们最终的结果 // 1. 排序 sort(nums.begin(), nums.end()); // 2. 利用双指针进行问题的解决 int n = nums.size(); for (int i = 0; i < n;) { // 固定数 a if (nums[i] > 0) { // 我们固定的数只选择小于 0 或者等于 0 的数字，不选择正数，这个是个小优化 break; } // 我们在固定数 i 后面的区间继续双指针的操作 int left = i + 1, right = n - 1, target = -nums[i]; // 我们在后面的区间只需要将 target 寻找到，看看是哪两个指针之和 while (left < right) { int sum = nums[left] + nums[right]; if (sum > target) { // 说明右边的那个数太大了，我们要往左挪动一位 right--; } else if (sum < target) { left++; } else { // 说明我们已经找到了最终的结果了 ret.push_back({nums[i], nums[left], nums[right]}); // 将我们最后得到的三元组的答案存放在 ret 中 left++, right--; // 这个就是保证没有情况漏掉，进一步缩小区间 // 去重 left 和 right while (left < right && nums[left] == nums[left - 1]) { // 如果下一个数字和前一个数字是相等的话我们一直进行加加的操作，直到我们的这个数和之前的数不相等了 left++; // 但是如果我们碰到了特殊情况的话，就是一组数字全是 0，然后我们这个 Left 就是有可能的造成越界的情况了，所以我们在移动的时候我们的 left 要小于 right } // 处理完 left 的重复和越界问题之后我们还要处理这个 right 的重复和越界问题 while (left < right && nums[right] == nums[right + 1]) { // nums[right]==nums[right+1] 这个就是重复元素，重复的话就进行这个 right-- 的操作 right--; } // 通过这两个 while 循环我们就能实现这个去重的操作了 } } // 当我们的内部循环第一个 while 循环结束后我们的第一个 i 所涉及到的三元组就全部找到了，那么我们接下来就对 i 进行去重操作 i++; while (i < n && nums[i] == nums[i - 1]) { i++; // 加到 nums[i] 和前面的数不相同，但是这个也存在越界的情况 } // 我们在这个 for 循环中我们的第三个条件我们可以不写 i++，可以空着，因为我们这里已经存在 i++ 的操作了 } return ret; } }; // 时间复杂度是 n^2 级别的，空间复杂度 logn

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ret; // 存放结果的数组 // 1. 排序 sort(nums.begin(), nums.end()); // 利用双指针解决问题 int n = nums.size(); for (int i = 0; i < n;) { // 固定数 a // 利用三数之和 for (int j = i + 1; j < n;) { // 固定数 b // 利用双指针 int left = j + 1, right = n - 1; long long aim = (long long)target - nums[i] - nums[j]; // 这个就是我们通过双指针要找到的两数之和 while (left < right) { int sum = nums[left] + nums[right]; if (sum < aim) { left++; } else if (sum > aim) { right--; } else { ret.push_back({nums[i], nums[j], nums[left++], nums[right--]}); // 固定的 a 和 b 以及 left 和 right 指向的值 // 找到一种结果之后我们进行缩小区间的操作继续进行寻找符合条件的数，我们在将结果存放到 ret 的时候进行 left++, right-- // 去重一：left 和 right 要跳过和之前相同的元素 while (left < right && nums[left] == nums[left - 1]) { left++; } // 相等的话我们就进行跳过的操作，并且我们保证不越界 while (left < right && nums[right] == nums[right + 1]) { right--; } } } // 去重二：现在我们对 b 进行去重的操作 j++; while (j < n && nums[j] == nums[j - 1]) { j++; // 保证不越界并且这个 ++ 后的数和之前的数是不相等的，如果相等的话就一直进行 ++ 操作，而且我们最上面的 for 循环中就不需要写 j++ 了，因为我们这里写了 } } // 去重三： i++; while (i < n && nums[i] == nums[i - 1]) { i++; // 同时我们上面的 for 循环也是不同进行 i++ 的 } } return ret; } };

算法题解：三数之和与四数之和

1. 三数之和

1.1 题目说明

示例 1

示例 2

示例 3

1.2 题目分析

更多推荐文章

相关免费在线工具

1.3 代码部分

1.4 代码分析

2. 四数之和

2.1 题目说明

示例 1

示例 2

2.2 题目分析

2.3 代码部分

2.4 代码解析

算法题解：三数之和与四数之和

1. 三数之和

1.1 题目说明

示例 1

示例 2

示例 3

1.2 题目分析

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

1.3 代码部分

1.4 代码分析

2. 四数之和

2.1 题目说明

示例 1

示例 2

2.2 题目分析

2.3 代码部分

2.4 代码解析