Leetcode 18. 4Sum

Leetcode_18.cpp

/* Watch video explanation on Youtube:  */
class Solution {
    vector<vector<int>> ans;   // Stores the final answer.
    
    /* Skip the duplicates. */
    int increment(vector<int>& nums, int cur) {
        int n = nums.size();
        int j=cur+1;
        while (j < n && nums[j] == nums[cur]) {
            j++;
        }
        return j;
    }
    
    /* Skip the duplicates. */
    int decrement(vector<int>& nums, int cur) {
        int j=cur-1;
        while (j >= 0 && nums[j] == nums[cur]) {
            j--;
        }
        return j;
    }
    
    /* Pairs of numbers in array `nums` from index `start` to
     * index `end` with sum `target`.
     */
    void twoSum(vector<int>& nums, int start, 
                int end, int target, int first, int second) {
        while (start < end) {
            if (nums[start]+nums[end] == target) {
                // Add the triplet in the answer.
                ans.push_back({first, second, nums[start], nums[end]}); 
                start = increment(nums, start);
                end = decrement(nums, end);
            } else if (nums[start]+nums[end] < target) {
                start = increment(nums, start);
            } else {
                end = decrement(nums, end);
            }
        }
    }
    
    void threeSum(vector<int>& nums, int start, 
                int end, int target, int first) { // O(n^2)
        for (int i=start; i<=end; i=increment(nums, i)) { // n *
            int second = nums[i]; // 1
            twoSum(nums, i+1, end, target-second, first, second); // O(n)
        }
    }
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) { // O(n^3)
        sort(nums.begin(), nums.end()); // O(nlogn)
        int n = nums.size(); // 1
        for (int i=0; i<n; i=increment(nums, i)) { // n *
            int first = nums[i]; // 1
            threeSum(nums, i+1, n-1, target-first, first); // O(n^2)
        }
        return ans;
    } // O(1)
};