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 > fourSum(vector &num, int target) {
        vector> result;
        int len=num.size();
        if(len<4){
            return result;
        }
        std::sort(num.begin(), num.end());
        for(int i=0; i0&&num[i]==num[i-1]){
                continue;
            }
            for(int j=i+1; ji+1&&num[j]==num[j-1]){
                    continue;
                }
                int start=j+1, end=len-1;
                while(start({num[i], num[j], num[start], num[end]}));
                        start++;    //这里记得加
                    }else if(sumj+1&&num[start]==num[start-1]&&start
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> twoSum(ArrayList pairs, int target){
    HashSet hashSet = new HashSet();
    int l = 0;
    int r = pairs.size()-1;
    ArrayList> res = new ArrayList>();
    while(l=rEnd;j--)
                {
                    if(check(pairs.get(i),pairs.get(j)))
                    {
                        ArrayList item = new ArrayList();
                        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> fourSum(vector& nums, int target) {
        std::sort(nums.begin(), nums.end());
        int len = nums.size();
        vector> result;
        
        for(int i=0; i0 && nums[i-1] == nums[i]){
                continue;
            }
            for(int j = i + 1; 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({nums[i], nums[j], nums[start], nums[end]}));
                        start++;
                    }else if(sum < target){
                        start++;
                    }else{
                        end--;
                    }
                    while(startj+1 && nums[start - 1] == nums[start]){
                        start++;
                    }
                    while(start

 
转载请注明： » [LeetCode] 4Sum

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->