LeetcodeHot100（6）三数之和

一、题目分析给定一个整数数组nums需要找到所有不重复的三元组(a, b, c)满足a b c 0三元组中三个元素的下标互不相同结果中不能包含重复的三元组例如[-1,0,1]和[0,-1,1]视为同一个三元组只保留一份二.核心思路排序法双指针法不能使用暴力枚举法时间复杂度为on3次方太复杂。先对数组进行一个从小到大的排序相同的数字挨着方便重复使用。然后固定一个数a然后a的下一个定义为左指针second 来找b最后一个元素定义为右指针third 来找c。目标找到 bc -a然后固定第一个数为a计算 bc是否等于-a。如果bc-a则结果偏大把右指针左移来减小数。如果bc-a结果偏小把左指针右移来增大数。直到bc -a时候把a和b、c提出来然后跳过和b、c重复的元素 继续寻找。直到左右指针重合了那么就让a移到下一个。继续找。遇到重复的a也跳过。直到某个a开始大于0了就不找了因为以后肯定都大于0了。class Solution { public: vectorvectorint threeSum(vectorint nums) { int n nums.size(); sort(nums.begin(),nums.end());//排序从小到大 vectorvectorint ans; //容器ans 存放一个整数容器 //枚举a for(int first 0; first n; first){ //如果a是相同的得跳过所以必须和上一次枚举的不同 if(first 0 nums[first] nums[first - 1]){ continue;//如果a和上一次的a一样就跳过此次循环 } //c对应最右 int third n-1; int target -nums[first]; //枚举b for(int second first 1;second n ;second){//second是a的下一个数 if(secondfirst1 nums[second] nums[second-1]){ continue;//如果b和上一次的b一样 也跳过 } //保证b在c的左侧 while(second third nums[second] nums[third]target){ --third; //如果三者的和大于零 就左移右指针 减小数值 } //如果指针重合 跳出循环 if(second third){ break; } //满足的记录下来 if(nums[second]nums[third] target){ ans.push_back({nums[first],nums[second],nums[third]}); } } } return ans; } };class Solution { public: vectorvectorint threeSum(vectorint nums) { //左右指针法 abc 0 sort(nums.begin(),nums.end()); int n nums.size(); vectorvectorint ans; for(int left 0;leftn;left){ //判断一下和上一个相等吗 if(left0nums[left-1]nums[left]) continue; int target -nums[left]; int b left 1; int c n-1; //b c的初始位置 while(bc){ if(b left1 nums[b] nums[b-1]) { b; continue; } if(c n-1 nums[c] nums[c1]) { c--; continue; } if(nums[b]nums[c] target){ b; } else if(nums[b]nums[c]target){ c--; } else { //满足条件 存起来 ans.push_back({nums[left],nums[b],nums[c]}); // b去重跳过所有和当前b相等的数 //while(b c nums[b] nums[b1]) b; // c去重跳过所有和当前c相等的数 // while(b c nums[c] nums[c-1]) c--; //收缩 b; c--; } } } return ans; } };