企业官网建设流程全解析

【算法学习笔记】LeetCode 15：三数之和（排序 + 双指针）

本文记录蓝桥杯 C++ B 组算法备赛过程中的一道经典算法题。

本题主要学习：数组排序、双指针、去重、时间复杂度分析。

一、题目信息

• 题目名称：三数之和（3Sum）
• 题目编号：LeetCode 15
• 算法标签：数组、排序、双指针
• 编程语言：C++
• 难度：中等

题目链接

LeetCode 中文站：

https://leetcode.cn/problems/3sum/description/

题目描述

给定一个整数数组nums，判断是否存在三个元素a、b、c，使得：

a+b+c==0

请找出所有满足条件且不重复的三元组。

注意：答案中不能包含重复的三元组。

输入示例

nums={-1,0,1,2,-1,-4};

输出示例

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

结果分析

满足条件的组合有两种：

第一种：

-1+(-1)+2=0

第二种：

-1+0+1=0

因此最终返回：

{{-1,-1,2},{-1,0,1}}

注意：不能重复使用数组中的同一个元素，也不能重复返回相同的三元组。

二、解题思路

1. 为什么不能使用三层 for 循环？

最直接的方法是使用三层循环：

for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){for(intk=j+1;k<n;k++){if(nums[i]+nums[j]+nums[k]==0){// 找到答案}}}}

这种方法需要枚举三个位置。

时间复杂度：

O(n^3)

当数组长度比较大时，效率不够理想。

因此，我们使用：

排序 + 双指针

将时间复杂度优化到：

O(n^2)

2. 第一步：对数组进行排序

首先：

sort(nums.begin(),nums.end());

原数组：

-1 0 1 2 -1 -4

排序之后：

-4 -1 -1 0 1 2

为什么要排序？

因为排序后数组具有单调性：

• 左边的数字比较小。
• 右边的数字比较大。

这样我们就可以根据三数之和的大小，决定移动哪个指针。

3. 第二步：固定第一个数字

使用外层循环：

for(inti=0;i<n-2;i++)

固定第一个数字：

nums[i]

然后使用两个指针寻找另外两个数字。

intleft=i+1;intright=n-1;

其中：

• i：固定第一个数字。
• left：从固定数字的右边开始。
• right：从数组末尾开始。

此时需要寻找：

nums[i]+nums[left]+nums[right]==0

4. 第三步：根据三数之和移动指针

这是本题最重要的部分。

计算：

intsum=nums[i]+nums[left]+nums[right];

分为三种情况：

情况一：sum > 0

说明三个数相加太大了。

因此需要让和变小：

right--;

情况二：sum < 0

说明三个数相加太小了。

因此需要让和变大：

left++;

情况三：sum == 0

说明找到了一组符合条件的答案：

res.push_back({nums[i],nums[left],nums[right]});

然后继续寻找下一组答案。

核心代码：

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

注意：这里必须使用if / else if / else，不能使用两个独立的if。

因为每轮循环只能根据当前的三数之和执行一种操作。

三、双指针过程图解

排序后的数组：

-4 -1 -1 0 1 2

假设固定：

i=1;nums[i]=-1;

初始状态：

下标： 0 1 2 3 4 5 数组： -4 -1 -1 0 1 2 i L R

第一次计算

-1+(-1)+2=0

找到第一组答案：

{-1,-1,2}

保存结果后，移动左右指针：

left++;right--;

此时：

下标： 0 1 2 3 4 5 数组： -4 -1 -1 0 1 2 i L R

第二次计算

-1+0+1=0

找到第二组答案：

{-1,0,1}

继续移动指针。

此时：

left >= right

内层循环结束。

最终结果：

{{-1,-1,2},{-1,0,1}}

四、去重操作（非常重要）

这道题最容易出错的地方之一就是去重。

因为题目要求不能返回重复的三元组。

1. 固定数字去重

代码：

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

例如：

-4 -1 -1 0 1 2

当i = 1时，固定数字为-1。

如果i = 2，发现：

nums[2]==nums[1]

说明固定数字重复了。

因此跳过：

continue;

避免重复寻找相同的三元组。

2. 左指针去重

代码：

while(left<right&&nums[left]==nums[left+1]){left++;}

如果左指针当前数字与后面的数字相同，就继续跳过。

3. 右指针去重

代码：

while(left<right&&nums[right]==nums[right-1]){right--;}

如果右指针当前数字与前面的数字相同，就继续跳过。

4. 找到答案之后移动指针

最后：

left++;right--;

这样就可以继续寻找下一组答案。

五、完整 C++ 代码

以下是本题最终整理的代码，使用 C++11 及以上标准。

#include<bits/stdc++.h>usingnamespacestd;classSolution{public:vector<vector<int>>threeSum(vector<int>&nums){// 第一步：排序sort(nums.begin(),nums.end());vector<vector<int>>res;intn=nums.size();// 数组不足三个元素，直接返回if(n<3){returnres;}// 第二步：固定第一个数字for(inti=0;i<n-2;i++){// 如果固定数字大于0，后面的数字只会更大if(nums[i]>0){returnres;}// 固定数字去重if(i>0&&nums[i]==nums[i-1]){continue;}// 第三步：定义左右指针intleft=i+1;intright=n-1;// 第四步：双指针寻找另外两个数字while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum>0){right--;}elseif(sum<0){left++;}else{// 找到符合条件的三元组res.push_back({nums[i],nums[left],nums[right]});// 右指针去重while(left<right&&nums[right]==nums[right-1]){right--;}// 左指针去重while(left<right&&nums[left]==nums[left+1]){left++;}// 继续寻找下一组答案left++;right--;}}}returnres;}};

六、测试用例及输出

测试用例 1：题目示例

输入：

nums={-1,0,1,2,-1,-4};

输出：

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

测试用例 2：没有符合条件的组合

输入：

nums={1,2,3,4};

输出：

[]

测试用例 3：全部为零

输入：

nums={0,0,0,0};

输出：

[[0,0,0]]

这里特别注意：虽然数组中有四个 0，但是只能返回一个不重复的三元组。

测试用例 4：存在大量重复数字

输入：

nums={-2,0,0,2,2};

输出：

[[-2,0,2]]

测试用例 5：数组长度不足

输入：

nums={0,1};

输出：

[]

七、时间复杂度和空间复杂度

时间复杂度

第一步排序：

O(n log n)

第二步外层循环：

O(n)

第三步双指针：

每次固定一个i，左右指针最多移动 O(n) 次。

因此：

O(n × n) = O(n²)

总体时间复杂度：

O(n²)

空间复杂度

不考虑返回结果数组：

• 双指针只使用常数个变量。
• 排序可能使用递归栈空间。

因此额外辅助空间通常记为：

O(log n)（考虑排序栈空间时）。

不计排序内部空间时，算法本身的额外空间为 O(1)。

八、本题容易犯的错误

错误 1：使用两个独立的 if

错误写法：

if(sum>0){right--;}if(sum<0){left++;}else{// 保存答案}

问题：

第一个 if 移动指针后，第二个 if 会重新判断，可能导致错误地保存不符合条件的组合。

正确写法：

if(sum>0){right--;}elseif(sum<0){left++;}else{// 保存答案}

错误 2：忘记固定数字去重

如果不判断：

nums[i]==nums[i-1]

可能得到重复的三元组。

错误 3：找到答案后不移动左右指针

如果找到答案后不执行：

left++;right--;

就可能一直停留在当前组合，造成死循环。

错误 4：不理解为什么移动指针

记住：

• 和太大，右指针左移。
• 和太小，左指针右移。
• 和等于 0，保存答案并继续寻找。

九、本题总结与收获

通过这道题，我掌握了以下知识：

1. 使用sort()对数组进行排序。
2. 理解排序后双指针的移动原理。
3. 使用外层循环固定一个数字。
4. 使用左右指针寻找另外两个数字。
5. 使用continue和while实现去重。
6. 理解if / else if / else的执行逻辑。
7. 将三层循环优化为排序 + 双指针，使时间复杂度从 O(n³) 降低到 O(n²)。

核心代码记忆

intsum=nums[i]+nums[left]+nums[right];if(sum>0){right--;}elseif(sum<0){left++;}else{res.push_back({nums[i],nums[left],nums[right]});left++;right--;}

个人学习心得

这道题一开始我尝试使用哈希表思路，但是后来发现排序 + 双指针更加适合这道题。

在独立编写代码的过程中，我曾经把两个独立的if写在一起，导致程序错误地保存了不满足三数之和为 0 的组合。

经过修改，我理解了if / else if / else的区别，也理解了为什么三数之和大于 0 时要移动右指针，小于 0 时要移动左指针。

这道题最大的收获不是记住代码，而是理解排序后双指针为什么能够正确地缩小搜索范围。

十、后续练习方向

建议继续练习以下题目：

LeetCode 题目链接：

• https://leetcode.cn/problems/two-sum/
• https://leetcode.cn/problems/3sum/
• https://leetcode.cn/problems/4sum/
• https://leetcode.cn/problems/3sum-closest/

备赛目标：2027 年第十八届蓝桥杯 C/C++ 程序设计大学 B 组，争取省一等奖。

持续记录每一道算法题的思路、代码、错误和总结，逐步建立自己的算法知识体系。

#蓝桥杯 #C++ #算法学习 #LeetCode #三数之和 #双指针 #数据结构与算法