Neat C++ code with helper function from twoSum


  • 0
    T
    class Solution {
    public:
        void twoSum(vector<int>&numbers,int begin, int first, int second, int target, vector<vector<int>>& ret){
            if(begin>=numbers.size()-1) return;
            int b=begin;
            int e=numbers.size()-1;
            while(b<e){
                int rest=numbers[b]+numbers[e];
                if(rest==target){
                    vector<int>tmp_ret;
                    tmp_ret.push_back(first);
                    tmp_ret.push_back(second);
                    tmp_ret.push_back(numbers[b]);
                    tmp_ret.push_back(numbers[e]);
                    ret.push_back(tmp_ret);
                
                do{b++;} 
                while(b<e && numbers[b]==numbers[b-1]);
                do{e--;}
                while(b<e && numbers[e]==numbers[e+1]);
                }
                
                else if (rest<target) ++b;
                else --e;
            }
        }
        
        
        
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
             vector<vector<int>>ret;
             if(nums.size()<=3) return ret;
             sort(nums.begin(), nums.end());
             for(int i=0; i<nums.size()-3; ++i){
                 if(i>0 && nums[i]==nums[i-1]) continue;
                 for(int j=i+1; j<nums.size()-2; ++j){
                     if(j>i+1 && nums[j]==nums[j-1]) continue;
                     twoSum(nums, j+1, nums[i], nums[j], target-(nums[i]+nums[j]), ret); 
                     //nums[i], nums[j] being the dummy, waiting to be passed into ret, not doing anything
    
                 }
             }
             return ret;
        }
    
    };
    

Log in to reply
 

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