(126)15. 三数之和(leetcode)

题目链接： https://leetcode-cn.com/problems/3sum/ 难度：中等 15. 三数之和 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？ 请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

今天每日一题是四数之和 哈哈 凑巧今天把三数之和也做了算了 刚做完四数之和在做三数之和是真的简单。。。

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; int n=nums.size(); if(n<3){ return res; } sort(nums.begin(),nums.end()); for(int i=0;i<n;++i){ if(i>0&&nums[i]==nums[i-1]){ continue; } if(i+2<n&&nums[i]+nums[i+1]+nums[i+2]>0){ break; } if(nums[i]+nums[n-1]+nums[n-2]<0){ continue; } int left=i+1,right=n-1; while(left<right){ int num=nums[i]+nums[left]+nums[right]; if(num<0){ left++; }else if(num>0){ right--; }else{ res.push_back({nums[i],nums[left],nums[right]}); while(left<right&&nums[left]==nums[left+1]){ left++; } left++; while(left<right&&nums[right]==nums[right-1]){ right--; } right--; } } } return res; } };