36ms C++ solution with 4th element reclusive search


  • 0
    W

    Method similar to 3Sum Closest reclusive solution
    Use a reclusive search function with O(log n) for search of the 4th element

    class Solution {
    private:
        //search if target is within nums in range start to end 
        //used to search for the 4th element
        bool _search(int target, vector<int>& nums,int start,int end)
        {
            if (start<0) return false;
            if (start>end) return false;
            if(target <nums[start] || target > nums[end]) return false;
            if(start ==end) return (target ==nums[start]);
            int c = (start+end)/2;
            if(nums[c]>target){
                return _search(target,nums,start,c-1);
            }else if (nums[c] <target){
                return _search(target,nums,c+1,end);
            }
            return true;
        }
    
        void _fourSum(vector<int>& nums, int target,vector<int>&sumList, vector<vector<int>>& result,int start)
        {
            if(nums.size()==0) return;
            int elementLeft = 4 - sumList.size();
            
            
            //avoid unnecessary process, return if the target is too small or too large 
            if(target < nums[start]*elementLeft ||target>nums[nums.size()-1]*elementLeft) return;
    
            
            if(sumList.size()==3)
            {
                if(_search(target,nums,start,nums.size()-1))
                {
                    sumList.push_back(target);
                    result.push_back(sumList);
                    sumList.pop_back();
                    return;
                }
                return;
            }
            //a number bigger than the whole list
            int last = nums[nums.size()-1]+1;
            
            for (int i=start;i<nums.size();i++)
            {
                if(last ==nums[i])continue;
                last =nums[i];
                sumList.push_back(nums[i]);
                _fourSum(nums,target-nums[i],sumList,result,i+1);
                sumList.pop_back();
            };
        }
    
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>>  result;
            vector<int>  temp;
            sort(nums.begin(),nums.end());
            _fourSum(nums,target,temp,result,0);
            return result;
        }
    };

  • 0
    Z

    I guess this is very slow, in theory. Interviewer won't love this.


Log in to reply
 

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