Appearance
18. 四数之和
原题链接：LeetCode 18. 四数之和
题目描述
给你一个由 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
难度： Medium
题解代码
javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
nums.sort((m, n) => m - n)
const res = []
const len = nums.length
for (let i = 0; i < len; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
if ((nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3]) > target) break
if ((nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3]) < target) continue
for (let j = i + 1; j < len; j++) {
if(j > i + 1 && nums[j] === nums[j - 1]) continue
let left = j + 1
let right = len - 1
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right]
if (sum === target) {
res.push([nums[i], nums[j], nums[left], nums[right]])
while(left < right && nums[left] === nums[left + 1]) {
left++
}
while(left < right && nums[right] === nums[right - 1]) {
right --
}
left++
right--
} else if (sum < target) {
left++
} else {
right--
}
}
}
}
return res
};