【Hot 100 刷题计划】 LeetCode 15. 三数之和 | C++ 排序+双指针
LeetCode 15. 三数之和
📌 题目描述
题目级别：中等
给你一个整数数组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]]
💡 破题思路：排序 + 固定一端 + 双指针夹逼
这道题如果用暴力三层 for 循环，时间复杂度是O(N3)O(N^3)O(N3)，绝对会超时。而且暴力法极难处理“不重复的三元组”这个要求。
最高效的解法是降维打击：把O(N3)O(N^3)O(N3)降为O(N2)O(N^2)O(N2)。
核心流程如下：
- 先排序（极其关键）：
排序是双指针夹逼的前提，也是轻松跳过重复元素的基石。 - 固定第一个数 (
nums[i])：
遍历数组，将nums[i]作为三元组中最小的那个数固定下来。此时问题就变成了：在i之后的数组中，寻找两个数，使它们的和等于-nums[i]（这就是经典的《两数之和 II》问题）。 - 双指针向中间夹逼：
设左指针l = i + 1，右指针r = n - 1。- 如果
sum == 0，记录答案，并让l和r同时向中间收缩。 - 如果
sum < 0，说明总和太小，左指针l右移以增大数值。 - 如果
sum > 0，说明总和太大，右指针r左移以减小数值。
- 如果
- 地狱级细节：三重去重：
- 去重 1 (外层)：如果当前的
nums[i]和上一个固定过的nums[i-1]一样，直接continue跳过，因为同样的开头一定会搜出同样的结果。 - 去重 2 & 3 (内层)：当找到一组正确答案后，左指针
l必须跳过身后所有与之重复的元素，右指针r也必须跳过身前所有与之重复的元素，否则三元组会重复！
- 去重 1 (外层)：如果当前的
💻 C++ 代码实现 (最强双指针模板)
classSolution{public:vector<vector<int>>threeSum(vector<int>&nums){intn=nums.size();// 1. 必须先排序，为双指针夹逼和去重打下基础sort(nums.begin(),nums.end());vector<vector<int>>res;// 2. 遍历数组，固定第一个数 nums[i]for(inti=0;i<n;i++){// 去重点 1：如果固定的这个数和上一次固定的数一样，直接跳过，防止产生重复三元组if(i&&nums[i]==nums[i-1])continue;// 定义左右双指针intl=i+1,r=n-1;// 3. 双指针开始向中间夹逼while(l<r){intsum=nums[i]+nums[l]+nums[r];if(sum==0){// 找到一组符合条件的解，塞入结果集res.push_back({nums[i],nums[l],nums[r]});// 去重点 2：左指针跳过所有重复元素while(l<r&&nums[l]==nums[l+1])l++;// 去重点 3：右指针跳过所有重复元素while(l<r&&nums[r]==nums[r-1])r--;// 双双往中间聚拢一步，寻找下一个潜在的组合l++,r--;}// sum 太小，左指针右移找更大的数elseif(sum<0)l++;// sum 太大，右指针左移找更小的数elser--;}}returnres;}};