LeetCode [18] 4Sum

18. 4Sum

Medium

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

//C++
//C++:method1 116ms
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for(int i=0; i<n; ++i){
            if(i && nums[i]==nums[i-1]) continue;
            for(int j=i+1; j<n; ++j){
                if(j>i+1 && nums[j]==nums[j-1]) continue;
                int l = j+1, r = n-1;
                while(l<r){
                    if(l>j+1 && nums[l]==nums[l-1]){l++; continue;}
                    int sum = nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum==target){
                        vector<int> vec = {nums[i], nums[j], nums[l], nums[r]};
                        ret.push_back(vec);
                        l++;
                        r--;
                    }else if(sum<target){
                        l++;
                    }else{
                        r--;
                    }
                }
            }
        }
        return ret;
    }
};

class Solution {
    struct nd{
          int i, j, val;
          nd(int ii,int jj,int v):i(ii), j(jj), val(v){}
    };
    bool valid(int a,int b,int c,int d){
        return a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d;
    }
    struct hs{
        size_t operator ()(const vector<int> &v)const {
            int t=0;
            for(int i=0;i<4;i++){
                t*=9997;
                t+=v[i];
            }
            return t;
        }
    };
    struct equal{
        bool operator ()(const vector<int> &v1,const vector<int> &v2) const
        {
            for(int i=0;i<4;i++){
                if(v1[i]!=v2[i])
                    return false;
            }
            return 1;
        }
    };
    
    unordered_map<int,vector<nd> > hash;
    vector<vector<int> > res;
    unordered_set<vector<int>, hs, equal> reps;
    vector<nd> pairs;
    
public:    
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        for(int i=0;i<num.size();i++){
            for(int j=i+1;j<num.size();j++){
                pairs.push_back(nd(i,j,num[i]+num[j]));
            }
        }
        
        for(int i=0; i<pairs.size(); ++i){
            int v = pairs[i].val;
            int u = target-v;
            if(hash.find(u)==hash.end()){
                hash[v].push_back(pairs[i]);
            }else{
                for(int j=0; j<hash[u].size(); ++j){
                    if(valid(pairs[i].i,pairs[i].j,hash[u][j].i,hash[u][j].j)){
                        vector<int> r(4);
                        r[0]=num[pairs[i].i];
                        r[1]=num[pairs[i].j];
                        r[2]=num[hash[u][j].i];
                        r[3]=num[hash[u][j].j];
                        sort(r.begin(), r.end());
                    
                        if(reps.find(r)==reps.end()){
                            res.push_back(r);
                            reps.insert(r);
                        }
                    }
                }
                hash[v].push_back(pairs[i]);
            }
        }    
        return res;
    }
};

//Java
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for(int i=0; i<nums.length; ++i){
            if(i>0 && nums[i]==nums[i-1]) continue;
            for(int j=i+1; j<nums.length; ++j){
                if(j>i+1 && nums[j]==nums[j-1]) continue;
                int l = j+1, r = nums.length-1;
                while(l<r){
           //         System.out.println(i+" "+j+" "+l+" "+r);
                    if(l>j+1 && nums[l]==nums[l-1]){
                        l++;
                        continue;
                    } 
                    int s = nums[i]+nums[j]+nums[l]+nums[r];
                    if(s==target){
                        ret.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        l++;
                        r--;
                    }else if(s<target){
                        l++;
                    }else{
                        r--;
                    }
                }
            }
        }
        return ret;
    }
}