2sum 问题是,给出一个数组,从里面找出 2 个元素,使其相加之和等于 target。
3sum 问题是,给出一个数组,从里面找出 3 个元素,使其相加之和等于 target。
以此类推,nsum 的问题是,从数组中找出 n 个元素,使其相加之和等于 target。那怎么求解这个问题的答案呢?
直接给出代码,如下:
var threeSum = function (nums) {
nums.sort((a, b) => a - b)
let len = nums.length
let res = nsum(3, 0, len - 1, 0)
return res
function nsum(n, low, high, target) {
let res = []
if (n === 2) {
while (low < high) {
let left = nums[low]
let right = nums[high]
let sum = left + right
if (sum === target) {
res.push([nums[low], nums[high]])
while (left === nums[low]) low++
while (right === nums[high]) high--
} else if (sum > target) {
high--
} else {
low++
}
}
} else {
for (let i = low; i <= len - n; i++) {
let v = nsum(n - 1, i + 1, len - 1, target - nums[i])
let num = nums[i]
if (v.length) {
for (let item of v) {
res.push([num, ...item])
}
}
while (nums[i + 1] === num) i++
}
}
return res
}
}