ReaL simple c++ solution with in-line comments


  • 1
    M
    class Solution {
    public:
    
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> ans;
            int len=nums.size();
            if (len < 4) return ans; // you want 4-sum, right?
            
            /* idea: travers first and second numbers, then use o(n) to find third and fourth numbers 
               
               o(n) algorithm: when array is sorted, let c=0, d=len-1. if n[c]+n[d]<target, we know n[d] can never be 
                    answer, since n[c] is alreayd smallest but the sum is still > target. similarly, when sum>target, c+=1. 
            */
    
            sort(nums.begin(), nums.end());
            
            for (int a=0; a<len-3; next_diff(nums, a))
                for (int b=a+1; b<len-2; next_diff(nums, b)) {
                    
                    int c=b+1, d=len-1;
                    int tar=target-nums[a]-nums[b];
                    
                    while (c<d) {
                        int sum=nums[c]+nums[d];
                        if (sum>tar)
                            prev_diff(nums, d);
                        else if (sum<tar)
                            next_diff(nums, c);
                        else {
                            vector<int> sub;
                            sub.push_back(nums[a]);
                            sub.push_back(nums[b]);
                            sub.push_back(nums[c]);
                            sub.push_back(nums[d]);
                            ans.push_back(sub);
                            prev_diff(nums, d);
                            next_diff(nums, c);
                        }
                    }
                }
            return ans;
        }
        
        /* to remove duplicate answers: */
        void next_diff(vector<int>& nums, int& p) {
            int val=nums[p++]; 
            while (p<nums.size())
                if (nums[p]==val) p++;
                else break;
        }
        
        void prev_diff(vector<int>& nums, int& p) {
            int val=nums[p--];
            while (p>=0)
                if (nums[p]==val) p--;
                else break;
        } 
    };

Log in to reply
 

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