c++ O(n^3) 56ms


  • 0
    A

    Thanks to 3-Sum question, we can copy the same way to solve 4-Sum problem.

    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> result;
            
            if(nums.size()<4)
                return result;
                
            std::sort(nums.begin(), nums.end());  //sort the array.
            
            int n = nums.size();
            
            int i,j;
            for(i=0; i<n; ++i) {
                for(j=n-1; j>0; --j ) {
                
                if((i>0&&nums[i]==nums[i-1]) || (j<n-1&&nums[j]==nums[j+1]))
                    continue;
                    
                    
                    int low = i+1;
                    int high = j-1;
                
                  while(low<high) {
                     if(nums[i]+nums[low]+nums[high]+nums[j] > target)
                            high--;
                     else if(nums[i]+nums[low]+nums[high]+nums[j] < target)
                            low++;
                     else {
                            vector<int> tmp;
                            tmp.push_back(nums[i]);
                            tmp.push_back(nums[low]);
                            tmp.push_back(nums[high]);
                            tmp.push_back(nums[j]);
                            result.push_back(tmp);
                        
                            while(low<high && nums[low]==nums[low+1])
                                low++;
                            while(low<high && nums[high]==nums[high-1])
                                high--;
                            
                            low++;
                            high--;
                        }
                    }  
                }
            
            }
            
            return result;
        }
    };
    

Log in to reply
 

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