Leetcode 3Sum problem solution in C++ programming

In the Leetcode 3Sum problem solution in C++ programming Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Leetcode 3Sum problem solution in C++ programming

class Solution {
private:
    void findThreeNums(vector<int> &nums, int index, vector<vector<int>> &results){
        int low  = index + 1;
        int high = nums.size() - 1;
        
        while(low < high){
            int k = nums.at(index) + nums.at(low) + nums.at(high);
            
            if(k > 0) high--;
            else if(k  < 0) low++;
            else if(k == 0){
                results.push_back({nums.at(index), nums.at(low++), nums.at(high--)});
                while(low < high && nums.at(low - 1) == nums.at(low)) low++;
            }
        }
    }
    
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> results;
        
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++){
            if(i == 0 || nums.at(i - 1) != nums.at(i))
                findThreeNums(nums, i, results);
            
            // once we get to a point in our array where its only positive numbers
            // we break, because it's not possible to obtain 0 with only positive numbers
            if(nums.at(i) >= 0) break;
        }
        
        return results;        
    }
};

Also read,

By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.

Leave a Reply

Your email address will not be published. Required fields are marked *