18-四数之和
标签：数组 双指针 排序
题目信息
题目地址： 18. 四数之和
题目内容：
javascript
给你一个由n个整数组成的数组nums，和一个目标值target。
请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]
（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0输
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
题解
解法一
思路：
和三数之和思路类似
由于多了一个数，所以外面需要
2层for循环，然后再处理一些边界问题时要额外注意1、对最外层的
i进行减枝操作时，要注意，一定要num[i] >= 0并且num[i] > target才能中断循环，而不是num[i] > target，因为不知道target是正数还是负数例如：
nums = [-5, -3, -2, -1, 3, 2, ...]，当target为-8时，比如nums[i]为-5时，大于target，此时不能直接返回，因为[-5,-3,-2,2]的和是等于-8的，这里就是要考虑target为负数的情况2、对
j进行减枝操作时，要注意，比较和target的大小时，是nums[i] + nums[j]去比较，并且nums[i] + nums[j]也要大于等于03、对
j进行去重时，j要大于i+1，因为j是从i + 1位置开始遍历的
代码实现：
javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const len = nums.length
if(len < 4) return []
nums.sort((a, b) => a - b)
// 从小到大排序后 如果最小的数字是正数并且大于等于target了 那么就不可能有符合的其他选项了
if(nums[0] > 0 && nums[0] >= target) return []
const res = []
for(let i = 0; i < len; i++) {
const iValue = nums[i]
// i进行减枝操作
if(iValue >= 0 && iValue > target) break
// 对i进行去重
if(i > 0 && iValue === nums[i - 1]) {
continue
}
for(let j = i + 1; j < len; j++) {
const theFirstToEndSum = nums[i] + nums[j]
// j减枝操作
if(theFirstToEndSum > target && theFirstToEndSum >= 0) break
// 对j进行去重
if(j > i + 1 && nums[j] === nums[j - 1]) {
continue
}
// 下面的逻辑和三数之和一样
let left = j + 1, right = len - 1
while(left < right) {
const sum = theFirstToEndSum + nums[left] + nums[right]
if(sum > target) {
right--
continue
}
if(sum < target) {
left++
continue
}
res.push([nums[i], nums[j], nums[left], nums[right]])
// 对left去重
while(nums[left] === nums[left + 1]) {
left++
}
// 对right去重
while(nums[right] === nums[right - 1]) {
right--
}
left++
right--
}
}
}
return res
};