三数之和 双指针 - 青衣怒马 - D1h.Net第一号博客
 






lazy pig~

青灯古佛,不见笑傲江湖...
 
 

Powered by D1h.Net第一号博客
D1h.Net第一号博客 | 首页 | 新随笔 | 联系 | 订阅 订阅 | 管理

三数之和 双指针

 

 

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { //排序后 对于每个nums[i],用双指针从nums[i]后面求是否有两个数的和等于-nums[i] //因为为了去重所以需要从nums[i]之后双指针,否则对于同一个结果会有重复 //nums[i]>0直接结束 因为后面也都大于0了,肯定和不为0 //如果nums[i]=nums[i-1]则直接跳过,因为后面能组成的结果都被前一个试过了,不跳过就重复 //匹配了之后 因为排过序了 相同的值会挤在一起,所以左右指针都要前进直到不重复了 //前进的时候限定条件也是l<r,保证在窗口内,如果限定l<nums.size()或r>=0则在判断的时候会出现当l为numss.size()-1的时候l+1为nums.size()数组越界,r也是同样的。 vector<vector<int>> res; sort(nums.begin(),nums.end()); for(int i=0;i<nums.size();i++) { if(nums[i]>0) break; if(i>0 && nums[i]==nums[i-1]) continue; int l=i+1; int r=nums.size()-1; while(l<r) { int sum=nums[i]+nums[l]+nums[r]; if(sum==0) { vector<int> temp; temp.push_back(nums[i]); temp.push_back(nums[l]); temp.push_back(nums[r]); res.push_back(temp); while(l<r && nums[l+1]==nums[l]) l++; while(l<r && nums[r]==nums[r-1]) r--; l++; r--; } else if(sum<0) l++; else if(sum>0) r--; } } return res; } };

 

每天进步一点点~
发表于 2021-09-08 19:38  青衣怒马  阅读(3)  评论(0编辑  收藏  举报
 

问答 28u iTmz.Net 3q科技 A8团队1 A8团队2 A8团队3 A8备