18. 4Sum

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]
]
题意：给定一个数字数组和一个目标值，找出所有4项组合使得四项相加等于目标值
代码如下：

var fourSum = function(nums, target) {
    var len=nums.length;
    var res=[];
    if(nums.length<4 || !nums) return res;
    if(len===4 && nums[0]+nums[1]+nums[2]+nums[3]==target) return [nums];
    //排序
    nums=nums.sort(function(a,b){return a-b;})
    
    for(var i=0;i<len-3;i++){
        //判断相等项
        // if(nums[i]===nums[i-1]) continue;
        for(var j=i+1;j<len-2;j++){
            if(j>i+1 && nums[j]===nums[j-1]) continue;
            var start=j+1,end=len-1;
            while(start<end){
                var sum=nums[i]+nums[j]+nums[start]+nums[end];
                if(sum===target){
                       res.push([nums[i],nums[j],nums[start],nums[end]])  
                    ++start;
                    --end;
                }else if(nums[i]+nums[j]+nums[start]+nums[end]>target){
                    --end;
                }else{
                    ++start;
                }
            }
        }
    }
   //去重
    var hash = {};  
    var result = [];  
    res.forEach(item=>{
        if(!hash[item]){
            result.push(item);
            hash[item]=true;
        }
    })
    return result;
};