My C++ solution of O(n^2) time complexity (accepted & without hash map)


  • 3
    C

    Here are my thoughts:
    Analysis: if we use brute-search to find the solution, clearly, the solution would be O(n^3), since we should consider all combinations of three numbers. And there is definitely not an efficient algorithm.

    So I considered to reduce the case into 2 sums: a+b+c = 0 <=> a+b = -c. And for a sorted array, we can accomplish a 2-sum problem in O(n) time. For 3-sum, it is equivalent to n 2-sum problems( consider a 2-sum problem for each number ). So here we get a time complexity of O(nlogn) + O(n^2), that is O(n^2).

    The most difficult problem I encountered is the duplicate in results. To accomplish this, we need to make better use of the fact that we have already sorted the vector, which means there should be no duplicates in the result if we use it correctly. And as a result, we do not need to de-duplicate the result we get. ( And I don't know why I got time limit exceeded, if I simply compare each two pairs of the result vector and delete the duplicates. Isn't it also O(n^2)? Can anyone help me?)

    ------------------------------------------------Start of Func-----------------------------------------------

     vector<vector<int> > threeSum(vector<int> &num) {
                    vector<vector<int>>result;
                    
                    if( !num.size() )   return result;
                    
                    sort( num.begin(), num.begin()+num.size() );
                    
                    //reduce the case to 2 variables
                    //for each num c, we have a+b+c=0 iff a+b=-c
                    for( int i=0; i<num.size(); i++ )
                    {         
                        if( i>=1 && num[i]==num[i-1] )   continue;
                                
                        int m=i+1, n=num.size()-1;
                        
                        while( m<n ) 
                        {
                            //only use the first m if there is a series of same num
                            if( m > i+1 && num[m]==num[m-1] ){
                                m++;
                                continue;
                            }
                            
                            //only use the last n if there is a series of same num
                            if( n < num.size()-1 && num[n]==num[n+1] ){
                                n--;
                                continue;
                            }
                            
                            if( num[m] + num[n] == -num[i] )
                            {
                                vector<int>temp;
                                
                                temp.push_back( num[i] );
                                temp.push_back( num[m] );
                                temp.push_back( num[n] );
                                result.push_back( temp );
                                
                                m++;
                                n--;
                            }
                            else if( num[m] + num[n] > -num[i] )
                            {
                                n--;
                            }
                            else
                            {
                                m++;
                            }
                        }
            
                    }
                    
                    return result;
                }
    

    ------------------------------------------End of Func-----------------------------------------------


  • 0
    T

    If you simply compare each two pairs of the result vector and delete the duplicates, it takes O(n^3) as the comparison of two vectors takes O(n) time.


Log in to reply
 

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