康瑞部落

4Sum

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

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)

• The solution set must not contain duplicate quadruplets.

    For example, given array S = {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)

解题思路：

1、基于3sum思想，外面再套一层，因此时间复杂度为O(n^3)，空间复杂度为O(1)。代码如下：

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int>> result;
        int len=num.size();
        if(len<4){
            return result;
        }
        std::sort(num.begin(), num.end());
        for(int i=0; i<len; i++){
            if(i>0&&num[i]==num[i-1]){
                continue;
            }
            for(int j=i+1; j<len; j++){
                if(j>i+1&&num[j]==num[j-1]){
                    continue;
                }
                int start=j+1, end=len-1;
                while(start<end){
                    int sum=num[i]+num[j]+num[start]+num[end];
                    if(sum==target){
                        result.push_back(vector<int>({num[i], num[j], num[start], num[end]}));
                        start++;    //这里记得加
                    }else if(sum<target){
                        start++;
                    }else{
                        end--;
                    }
                    while(start>j+1&&num[start]==num[start-1]&&start<end){
                        start++;
                    }
                    while(end<len-1&&num[end]==num[end+1]&&start<end){
                        end--;
                    }
                }
            }
        }
        return result;
    }
};

2、网上有另外一种办法，就是利用二分法，将num里面的元素两两相加组成一个元素，然后根据2sum的方法来求，相当于2num中有O(n^2)个数。2sum的时间复杂度为O(nlogn)，因此这种方法的4sum的时间复杂度为O(n^2logn^2)=O(n^2logn)，比第一种方法要优，但是空间复杂度为O(n^2)。Java代码转自http://blog.csdn.net/linhuanmars/article/details/24826871。

private ArrayList<ArrayList<Integer>> twoSum(ArrayList<Pair> pairs, int target){
    HashSet<Tuple> hashSet = new HashSet<Tuple>();
    int l = 0;
    int r = pairs.size()-1;
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    while(l<r){
        if(pairs.get(l).getSum()+pairs.get(r).getSum()==target)
        {
            int lEnd = l;
            int rEnd = r;
            while(lEnd<rEnd && pairs.get(lEnd).getSum()==pairs.get(lEnd+1).getSum())
            {
                lEnd++;
            }
            while(lEnd<rEnd && pairs.get(rEnd).getSum()==pairs.get(rEnd-1).getSum())
            {
                rEnd--;
            }
            for(int i=l;i<=lEnd;i++)
            {
                for(int j=r;j>=rEnd;j--)
                {
                    if(check(pairs.get(i),pairs.get(j)))
                    {
                        ArrayList<Integer> item = new ArrayList<Integer>();
                        item.add(pairs.get(i).nodes[0].value);
                        item.add(pairs.get(i).nodes[1].value);
                        item.add(pairs.get(j).nodes[0].value);
                        item.add(pairs.get(j).nodes[1].value);
                        //Collections.sort(item);
                        Tuple tuple = new Tuple(item);
                        if(!hashSet.contains(tuple))
                        {
                            hashSet.add(tuple);
                            res.add(tuple.num);
                        }
                    }                        
                }
            }
            l = lEnd+1;
            r = rEnd-1;
        }
        else if(pairs.get(l).getSum()+pairs.get(r).getSum()>target)
        {
            r--;
        }
        else{
            l++;
        }
    }
    return res;
}
private boolean check(Pair p1, Pair p2)
{
    if(p1.nodes[0].index == p2.nodes[0].index || p1.nodes[0].index == p2.nodes[1].index)
        return false;
    if(p1.nodes[1].index == p2.nodes[0].index || p1.nodes[1].index == p2.nodes[1].index)
        return false;
    return true;
}

二次刷题（2015-08-18）

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());
        int len = nums.size();
        vector<vector<int>> result;
        
        for(int i=0; i<len; i++){
            if(i>0 && nums[i-1] == nums[i]){
                continue;
            }
            for(int j = i + 1; j<len; j++){
                if(j > i + 1 && nums[j - 1] == nums[j]){
                    continue;
                }
                int start = j + 1, end = len - 1;
                while(start < end){
                    int sum = nums[i] + nums[j] + nums[start] + nums[end];
                    if(sum == target){
                        result.push_back(vector<int>({nums[i], nums[j], nums[start], nums[end]}));
                        start++;
                    }else if(sum < target){
                        start++;
                    }else{
                        end--;
                    }
                    while(start<end && start>j+1 && nums[start - 1] == nums[start]){
                        start++;
                    }
                    while(start<end && end<len-1 && nums[end] == nums[end + 1]){
                        end--;
                    }
                }
            }
        }
        
        return result;
    }
};