class Solution {
public:
    void twoSum(vector<int>& nums, int target, int left, vector<vector<int>>& result) {
        int l = left;
        int r = nums.size() - 1;

        while(l < r) {
            int sum = nums[l] + nums[r];
            if(target > sum) {
                l++;
            } else if (target < sum) {
                r--;
            } else {
                result.push_back({-target, nums[l], nums[r]});
                l++;
                r--;
                while(nums[l] == nums[l-1] && l < r) l++;
                while(nums[r] == nums[r+1] && l < r) r--;

            }
        }
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> result;

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

        for(int i = 0; i < n-2 && nums[i] <= 0; i++) {
            if(i == 0 || nums[i] != nums[i-1])
                twoSum(nums, -nums[i], i+1, result);
        }

        return result;
    }
};