15. 3Sum ( Leetcode )

    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        int size = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < size; i++)
        {
            int target = -1 * nums[i];
            int start = i+1, end = size-1;
            while(start < end)
            {
                if(nums[start] + nums[end] == target)
                {
                    ans.push_back({nums[i], nums[start], nums[end]});
                    while(start < end && nums[start] == nums[start + 1]) start++;
                    while(start < end && nums[end] == nums[end - 1]) end--;
                    start++;
                    end--;
                }
                else if(nums[start] + nums[end] > target)
                {
                    end--;
                }
                else
                {
                    start++;
                }
            }

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

        return ans;
    }