Easy C++ Solution, 3 loops //commented


  • 0
    C

    '''
    class Solution {
    public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> results;

        int n = nums.size();
        
        // return empty if less than 3 numbers in total 
        if(n < 3) return results;
        
        // sort first
        sort(nums.begin(), nums.end());
        
        // pick the 1st number
        for(int i = 0; i < n -2; i++ )  {
            
            // pick the 2nd number to be the next of 1st number then increment by 1
            for(int j = i+1; j < n-1; j++) {
                
                int sumofTwo = nums[i] + nums[j];
                
                // pick the 3rd number to be the next of 2nd number then increment by 1 
                for(int k = j + 1; k < n; k++ ) {
                    
                    // skip duplicate 3rd numbers
                    while(nums[k]== nums[k+1]) k++;
                    int sumofThree = (sumofTwo + nums[k]);
                    
                    if(  sumofThree== 0 ) {
                        // yes! found one, push to the results
                        vector<int> temp;
                        temp.push_back(nums[i]);
                        temp.push_back(nums[j]);
                        temp.push_back(nums[k]);
                        results.push_back(temp);
                        
                    } else if ( sumofThree > 0 ) {
                        
                        // exit loop of remaining 3rd number if sum of 3 exceed 0 because the list is alr sorted 
                        break;
                        
                    }
                    
                // skip duplicate 2nd numbers
                while(nums[j]== nums[j+1]) j++; 
                    
                    
                }
                // skip the duplicate 1st, it is put at the back to allow the 1st and 2nd number to be the same  eg. -1 -1 0
                while(nums[i]== nums[i+1]) i++;
            }
        }
        
        
        return results;
        
    }
    

    };
    '''


  • 0
    Z

    In skipping duplicate numbers, index may be out of range in some cases.


  • 0
    A

    @zx731 You're right I don't think it's supposed to normally pass all cases. Should have these conditions instead:

    while (k < n - 1 && nums[k] == nums[k + 1]) k++;
    while (j < n - 2 && nums[j] == nums[j + 1]) j++;
    while (i < n - 3 && nums[i] == nums[i + 1]) i++;  
    

    Going out of the bounds of the vector is supposed to have undefined behaviour.


Log in to reply
 

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