Leetcode 15. 3Sum (https://www.InterviewRecipes.com/3sum) (https://youtu.be/MmhfOzYMYPk)

Leetcode_15.cpp

/* Watch video explanation here: https://youtu.be/MmhfOzYMYPk */
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 a) {
        while (start < end) {
            if (nums[start]+nums[end] == target) {
                // Add the triple in the answer.
                ans.push_back({nums[start], nums[end], a}); 
                start = increment(nums, start);
                end = decrement(nums, end);
            } else if (nums[start]+nums[end] < target) {
                start = increment(nums, start);
            } else {
                end = decrement(nums, end);
            }
        }
    }
public:
    vector<vector<int>> threeSum(vector<int>& nums) { // Time: O(n^2)
        sort(nums.begin(), nums.end()); // O(nlogn)
        int n = nums.size();
        for (int i=0; i<n; i=increment(nums, i)) { // n * 
            int a = nums[i];
            twoSum(nums, i+1, n-1, -a, a); // O(n)
        }
        return ans;
    } // Space: O(1)
};