Simple solution using 3 pointers (no hashing)


  • 0
    C

    The stated problem is quite straight forward - find triplets in the array who's sum is 0.
    This can be reduced to the following subproblems:

    Given an index i, find pairs of indices j,k such that i != j != k such that nums[j] + nums[k] = -nums[i].
    Given two pairs (a, b) and (c, d) with sum -nums[i] , ensure that a != c and a != d and b != c and b != d

    Solution will be empty if nums.size() < 3.

    vector<vector<int>> threeSum(vector<int>& nums) {
    // create an empty solution set
            vector<vector<int>> soln;
    // base case where nums.size() < 3
            if(nums.size() < 3) return soln;
    // sort the array
            sort(nums.begin(), nums.end());
    // consider a triplet which includes element at index i
            for(int i = 0; i < nums.size() - 2; i++){
    /* If the element at index i is the same as the previous element, we can skip
    this element, since all triplets considering nums[i] as first element are 
    already found.
    */
                if(i > 0 && nums[i-1] == nums[i]) continue;
    /*
    consider a pair of indices (i+1, n-1) where n = nums.size()
    */
                int j = i+1, k = nums.size() -1;
    // we need to find a pair with sum = -nums[i]
                int sum = -nums[i];
    
                while(j < k){
    // sum of the current pair
                    int s = nums[j] + nums[k];
    // if the sum is less than the required sum, we increment j
                    if(s < sum) {
    // j is incremented in a loop to ensure that duplicate values are not considered
                        while(nums[j] == nums[j+1] && j < k) j++;
                        j++; continue;
                    }else if(s > sum){
    // k is decremented in a loop to ensure that duplicate values are not considered
                        while(nums[k] == nums[k-1] && k > j) k--;
                        k--; continue;
                    }
                    //cout << i <<' '<<j <<' '<<k<<endl;
                    vector<int> v;
    // add solution to set
                    v.push_back(nums[i]); 
                    v.push_back(nums[j]);
                    v.push_back(nums[k]);
                    soln.push_back(v);
    // increment j in a loop
                    while(nums[j] == nums[j+1] && j < k) j++;
    // decrement k in a loop
                    while(nums[k] == nums[k-1] && k > j) k--;
                    j++; k--;
                }
            }
            return soln;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.