/**
knakul853
**/
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        int n = (int)nums.size();
        vector<vector<int>>ans;

        sort(nums.begin(), nums.end());

        for( int i=0;i<n;i++)
        {
            int l = i+1;
            int r = n-1;
            int target = -nums[i];

            while( l < r )
            {
                int sm = (nums[l] + nums[r]);

                if( sm > target ) r--;
                else if( sm < target ) l++;

                else{
                    ans.push_back({nums[l], nums[r], nums[i]});

                    int skipLeft =nums[l];
                    int skipRight = nums[r];

                    while( l < r && skipLeft == nums[l] )l++;
                    while( l < r && skipRight == nums[r] )r--;
                }
            }

            while(i+1 < n && nums[i] == nums[i+1])i++;
        }

        return ans;
    }
};