18. 4Sum.md

18. 4Sum

leetcode - 18. 4Sum

Runtime: 28 ms, faster than 78.17% of C++ online submissions for 4Sum.

Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for 4Sum.

Just wrap 3Sum problem with one more outer loop.

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int N = nums.size();
        vector<vector<int>> ans;
        
        sort(nums.begin(), nums.end());
        
        for(int first = 0; first < N-3; first++){
            if(first > 0 && nums[first] == nums[first-1]) continue;
            for(int second = first+1; second < N-2; second++){
                if(second > first+1 && nums[second] == nums[second-1]) continue;
                int left = second+1, right = N-1;
                int curTarget = target - nums[first] - nums[second];
                // cout << first << " " << second << " " << left << " " << right << endl;
                while(left < right){
                    if(nums[left] + nums[right] == curTarget){
                        ans.push_back({nums[first], nums[second], nums[left], nums[right]});
                        while(left < right && nums[left] == nums[left+1]) left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }else if(nums[left] + nums[right] < curTarget){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        
        return ans;
    }
};

findNSum, recursive, optimized

Runtime: 8 ms, faster than 98.35% of C++ online submissions for 4Sum.

Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for 4Sum.

class Solution {
public:
    void findNSum(int l, int r, int target, int N, vector<int>& nums, vector<int>& result, vector<vector<int>>& results){
        if(r-l+1 < N || N < 2 || target < nums[l]*N || target > nums[r]*N){
            //r-l+1 < N: range's width should >= N
            return;
        }
        if(N == 2){
            while(l < r){
                if(nums[l] + nums[r] == target){
                    result.push_back(nums[l]);
                    result.push_back(nums[r]);
                    // cout << "result: " << endl;
                    // for(int i = 0; i < result.size(); i++){
                    //     cout << result[i] << " ";
                    // }
                    // cout << endl;
                    results.push_back(result);
                    //need to revert the push_back above for later use!
                    result.pop_back();
                    result.pop_back();
                    while(l < r && nums[l] == nums[l+1]){
                        l++;
                    }
                    l++;
                    while(l < r && nums[r] == nums[r-1]){
                        r--;
                    }
                    r--;
                }else if(nums[l] + nums[r] < target){
                    l++;
                }else{
                    r--;
                }
            }
        }else{
            //recursively reduce N
            //i <= r+1-N: because r-i+1 should >= N
            for(int i = l; i <= r+1-N; i++){
                //skip duplicate nums[i]
                if(i == l || (i > l && nums[i] != nums[i-1])){
                    result.push_back(nums[i]);
                    // cout << "i: " << i << ", nums[i]: " << nums[i] << ", [" << i+1 << ",  " << r  << "], target: " << target-nums[i] << " , N: " << N-1 << endl;
                    findNSum(i+1, r, target-nums[i], N-1, nums, result, results);
                    //need to revert the push_back above for later use!
                    result.pop_back();
                }
            }
        }
    };
    
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        // for(int i = 0; i < nums.size(); i++){
        //     cout << nums[i] << " ";
        // }
        // cout << endl;
        vector<int> result;
        vector<vector<int>> results;
        findNSum(0, nums.size()-1, target, 4, nums, result, results);
        return results;
    }
};