18. 四数之和（JS实现）

1 题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

2 思路
这道题还是利用了排序 + 双指针 + 散列表去重的方法解决，与三数之和相比多加了一层循环

3代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
if (nums.length < 4) return [];
nums.sort(function(a,b){
return a-b;
});

var map = {};
var result = [];
var sum;
var key;
var filterMap = {};
for (var i=0; i<nums.length-3; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;

var min = nums[i] + nums[i+1] + nums[i+2] + nums[i+3];
if (min > target) break; //*小的四个数加起来都太大，那么久彻底没戏了

var max = nums[i] + nums[nums.length-1] + nums[nums.length-2] + nums[nums.length-3];
if (max < target) continue; //当前数加上其余*大的三个数，仍然比较小，那么说明当前数太小了

for (var j=i+1; j<nums.length-2; j++) {
var left = j + 1;
var right = nums.length – 1;

while(left < right) {
sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
key = ” + nums[i] + nums[j] + nums[left] + nums[right];
if (!map[key]) {
result.push([nums[i], nums[j], nums[left], nums[right]]);
map[key] = true;
}
left++;
right–;
} else if (sum > target) {
right–;
} else {
left++;
}
}
}
}

return result;
};