12ms KSum, c++ code


  • 5
    S

    Thanks to the posts from others, it really helped me understand the problem!
    I really liked @rikimberley's example for validity checking at levels of K higher than 2 and I liked the approaches I've seen for turning the problem into a KSum problem. Now I won't have to re-write my answer if they make a 5 sum problem!

    class Solution {
    private:
        // Valid for K >= 2
        void KSum(int k, vector<int>& nums, int l, int r, int target, vector<vector<int>>& retVal, vector<int>& cur, int ci ) 
        {
            int i, mn, mx;
            int km1 = k - 1;
    
            if ( r-l+1 < k ) return;
            
            while ( l < r )
            {
                mn = nums[l];
                mx = nums[r];
                
                // If K minus 1 largest + min < target, move to larger
                if ( ( mn + km1*mx ) < target ) l++;
                // If K minus 1 smaller + max > target, move to smaller
                else if ( ( km1*mn + mx ) > target ) r--;
                // If K * min > target, stop looking
                else if ( k*mn > target ) break;
                // If K * min == target, reached the threshold, check then stop looking
                else if ( k*mn == target )
                {
                    if ( ( l + km1 <= r ) && ( mn == ( nums[l+km1] ) ) )
                    {
                        for ( i = 0; i < k; i++ ) cur[ci+i] = mn;
                        retVal.push_back( cur );
                    }
                    break;
                }
                // If K * max < target, stop looking
                else if ( k*mx < target ) break;
                // If K * max == target, reached the threshold, check then stop looking
                else if ( k*mx == target )
                {
                    if ( ( l <= r - km1 ) && ( mx == ( nums[r-km1] ) ) )
                    {
                        for ( i = 0; i < k; i++ ) cur[ci+i] = mx;
                        retVal.push_back( cur );
                    }
                    break;                
                }
                // If K == 2, we found a match!
                else if ( k == 2 )
                {
                    cur[ci] = mn;
                    cur[ci+1] = mx;
                    retVal.push_back( cur );
                    l++;
                    while ( ( l < r ) && ( nums[l] == mn ) ) l++;
                    r--;
                    while ( ( l < r ) && ( nums[r] == mx ) ) r--;
                }
                // Otherwise, convert the problem to a K-1 problem
                else
                {
                    cur[ci] = mn;
                    KSum( km1, nums, ++l, r, target - mn, retVal, cur, ci+1 );
                    while ( ( l < r ) && ( nums[l] == nums[l-1] ) ) l++;
                }
            }
        }
    
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) 
        {
            vector<vector<int>> lRetVal;
            vector<int> lQuad( 4, 0 ); // Pre-allocate the size of the result
    
            // Sort to provide a mechanism for avoiding duplicates
            sort( nums.begin(), nums.end() );
            
            KSum( 4, nums, 0, nums.size()-1, target, lRetVal, lQuad, 0 );
    
            return( lRetVal );        
        }
    };

  • 0
    Q

    @sganje
    I did some test and found that your program is so robust, that even some of the "else if" blocks can be omitted and still reach 16 ms
    here is the simplified version that should be memorized first:

        void KSum(int k, vector<int>& nums, int l, int r, int target, vector<vector<int>>& retVal, vector<int>& cur, int ci ) 
        {
            int i, mn, mx;
            int km1 = k - 1;
    
            if ( r-l+1 < k ) return;
            
            while ( l < r )
            {
                mn = nums[l];
                mx = nums[r];
                
                // If K minus 1*max + min < target, move to larger
                if ( ( mn + km1*mx ) < target ) l++;
                // If K minus 1 *min + max > target, move to smaller
                else if ( ( km1*mn + mx ) > target ) r--;
                else if ( k == 2 )
                {
                    cur[ci] = mn;
                    cur[ci+1] = mx;
                    retVal.push_back( cur );
                    l++;
                    while ( ( l < r ) && ( nums[l] == mn ) ) l++;
                    r--;
                    while ( ( l < r ) && ( nums[r] == mx ) ) r--;
                }
                // Otherwise, convert the problem to a K-1 problem
                else
                {
                    cur[ci] = mn;
                    KSum( km1, nums, ++l, r, target - mn, retVal, cur, ci+1 );
                    while ( ( l < r ) && ( nums[l] == nums[l-1] ) ) l++;
                }
            }
        }

  • 0
    D

    @quesder you didn't use the 'int i' in your code.


Log in to reply
 

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