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