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也必须跳过身前所有与之重复的元素否则三元组会重复 C 代码实现 (最强双指针模板)classSolution{public:vectorvectorintthreeSum(vectorintnums){intnnums.size();// 1. 必须先排序为双指针夹逼和去重打下基础sort(nums.begin(),nums.end());vectorvectorintres;// 2. 遍历数组固定第一个数 nums[i]for(inti0;in;i){// 去重点 1如果固定的这个数和上一次固定的数一样直接跳过防止产生重复三元组if(inums[i]nums[i-1])continue;// 定义左右双指针intli1,rn-1;// 3. 双指针开始向中间夹逼while(lr){intsumnums[i]nums[l]nums[r];if(sum0){// 找到一组符合条件的解塞入结果集res.push_back({nums[i],nums[l],nums[r]});// 去重点 2左指针跳过所有重复元素while(lrnums[l]nums[l1])l;// 去重点 3右指针跳过所有重复元素while(lrnums[r]nums[r-1])r--;// 双双往中间聚拢一步寻找下一个潜在的组合l,r--;}// sum 太小左指针右移找更大的数elseif(sum0)l;// sum 太大右指针左移找更小的数elser--;}}returnres;}};