nsum 问题求解

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
  }
}

参考链接

https://mp.weixin.qq.com/s/fSyJVvggxHq28a0SdmZm6Q

作者: 曾小乱

喜欢写点有意思的东西

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据