【算法学习笔记】LeetCode 15三数之和排序 双指针本文记录蓝桥杯 C B 组算法备赛过程中的一道经典算法题。本题主要学习数组排序、双指针、去重、时间复杂度分析。一、题目信息题目名称三数之和3Sum题目编号LeetCode 15算法标签数组、排序、双指针编程语言C难度中等题目链接LeetCode 中文站https://leetcode.cn/problems/3sum/description/题目描述给定一个整数数组nums判断是否存在三个元素a、b、c使得abc0请找出所有满足条件且不重复的三元组。注意答案中不能包含重复的三元组。输入示例nums{-1,0,1,2,-1,-4};输出示例[[-1,-1,2],[-1,0,1]]结果分析满足条件的组合有两种第一种-1(-1)20第二种-1010因此最终返回{{-1,-1,2},{-1,0,1}}注意不能重复使用数组中的同一个元素也不能重复返回相同的三元组。二、解题思路1. 为什么不能使用三层 for 循环最直接的方法是使用三层循环for(inti0;in;i){for(intji1;jn;j){for(intkj1;kn;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(inti0;in-2;i)固定第一个数字nums[i]然后使用两个指针寻找另外两个数字。intlefti1;intrightn-1;其中i固定第一个数字。left从固定数字的右边开始。right从数组末尾开始。此时需要寻找nums[i]nums[left]nums[right]04. 第三步根据三数之和移动指针这是本题最重要的部分。计算intsumnums[i]nums[left]nums[right];分为三种情况情况一sum 0说明三个数相加太大了。因此需要让和变小right--;情况二sum 0说明三个数相加太小了。因此需要让和变大left;情况三sum 0说明找到了一组符合条件的答案res.push_back({nums[i],nums[left],nums[right]});然后继续寻找下一组答案。核心代码if(sum0){right--;}elseif(sum0){left;}else{res.push_back({nums[i],nums[left],nums[right]});left;right--;}注意这里必须使用if / else if / else不能使用两个独立的if。因为每轮循环只能根据当前的三数之和执行一种操作。三、双指针过程图解排序后的数组-4 -1 -1 0 1 2假设固定i1;nums[i]-1;初始状态下标 0 1 2 3 4 5 数组 -4 -1 -1 0 1 2 i L R第一次计算-1(-1)20找到第一组答案{-1,-1,2}保存结果后移动左右指针left;right--;此时下标 0 1 2 3 4 5 数组 -4 -1 -1 0 1 2 i L R第二次计算-1010找到第二组答案{-1,0,1}继续移动指针。此时left right内层循环结束。最终结果{{-1,-1,2},{-1,0,1}}四、去重操作非常重要这道题最容易出错的地方之一就是去重。因为题目要求不能返回重复的三元组。1. 固定数字去重代码if(i0nums[i]nums[i-1]){continue;}例如-4 -1 -1 0 1 2当i 1时固定数字为-1。如果i 2发现nums[2]nums[1]说明固定数字重复了。因此跳过continue;避免重复寻找相同的三元组。2. 左指针去重代码while(leftrightnums[left]nums[left1]){left;}如果左指针当前数字与后面的数字相同就继续跳过。3. 右指针去重代码while(leftrightnums[right]nums[right-1]){right--;}如果右指针当前数字与前面的数字相同就继续跳过。4. 找到答案之后移动指针最后left;right--;这样就可以继续寻找下一组答案。五、完整 C 代码以下是本题最终整理的代码使用 C11 及以上标准。#includebits/stdc.husingnamespacestd;classSolution{public:vectorvectorintthreeSum(vectorintnums){// 第一步排序sort(nums.begin(),nums.end());vectorvectorintres;intnnums.size();// 数组不足三个元素直接返回if(n3){returnres;}// 第二步固定第一个数字for(inti0;in-2;i){// 如果固定数字大于0后面的数字只会更大if(nums[i]0){returnres;}// 固定数字去重if(i0nums[i]nums[i-1]){continue;}// 第三步定义左右指针intlefti1;intrightn-1;// 第四步双指针寻找另外两个数字while(leftright){intsumnums[i]nums[left]nums[right];if(sum0){right--;}elseif(sum0){left;}else{// 找到符合条件的三元组res.push_back({nums[i],nums[left],nums[right]});// 右指针去重while(leftrightnums[right]nums[right-1]){right--;}// 左指针去重while(leftrightnums[left]nums[left1]){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(sum0){right--;}if(sum0){left;}else{// 保存答案}问题第一个 if 移动指针后第二个 if 会重新判断可能导致错误地保存不符合条件的组合。正确写法if(sum0){right--;}elseif(sum0){left;}else{// 保存答案}错误 2忘记固定数字去重如果不判断nums[i]nums[i-1]可能得到重复的三元组。错误 3找到答案后不移动左右指针如果找到答案后不执行left;right--;就可能一直停留在当前组合造成死循环。错误 4不理解为什么移动指针记住和太大右指针左移。和太小左指针右移。和等于 0保存答案并继续寻找。九、本题总结与收获通过这道题我掌握了以下知识使用sort()对数组进行排序。理解排序后双指针的移动原理。使用外层循环固定一个数字。使用左右指针寻找另外两个数字。使用continue和while实现去重。理解if / else if / else的执行逻辑。将三层循环优化为排序 双指针使时间复杂度从 O(n³) 降低到 O(n²)。核心代码记忆intsumnums[i]nums[left]nums[right];if(sum0){right--;}elseif(sum0){left;}else{res.push_back({nums[i],nums[left],nums[right]});left;right--;}个人学习心得这道题一开始我尝试使用哈希表思路但是后来发现排序 双指针更加适合这道题。在独立编写代码的过程中我曾经把两个独立的if写在一起导致程序错误地保存了不满足三数之和为 0 的组合。经过修改我理解了if / else if / else的区别也理解了为什么三数之和大于 0 时要移动右指针小于 0 时要移动左指针。这道题最大的收获不是记住代码而是理解排序后双指针为什么能够正确地缩小搜索范围。十、后续练习方向建议继续练习以下题目题目主要知识点LeetCode 1两数之和哈希表LeetCode 15三数之和排序 双指针LeetCode 18四数之和排序 双指针LeetCode 16最接近的三数之和排序 双指针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 #三数之和 #双指针 #数据结构与算法