3Sum (LeetCode) | Solution Explained

3Sum.cpp

// https://leetcode.com/problems/3sum/
// Explanation:
// https://youtu.be/6WsddbKA_vg
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() < 3) {
            return res;
        }
        int target = 0;
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < nums.size() - 2; ++i) {
            
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            
            if(nums[i] > target) {
                break;
            }
            
            int left = i + 1;
            int right = nums.size() - 1;
            
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if(sum == target) {
                    res.push_back( {nums[i], nums[left], nums[right]});
                    
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    while(right > left && nums[right] == nums[right - 1]) right--;
                    left++, right--;                    
                } else if(sum < target) {
                    left++;
                } else {
                    right--;
                }                
            }            
        }
        return res;
    }
};