代码之家 › 专栏 › 技术社区 › Carl Edwards monkbroc

求一个数组中的一个或多个数相加是否等于某个数

loops algorithm javascript

Carl Edwards monkbroc · 技术社区 · 6 年前

[1,2,4,6,3,9] . 我在想,什么是最好的循环方法,看看其中一个或多个可以加起来9。我最初的想法是:

检查当前数组索引值是否等于
如果当前数字小于magicNum,则将其与数组中的另一个数字相加,并保持循环以查看是否匹配
如果上面的不起作用,转到下一个号码并重复。

const magicNum = 9;

const arr = [10,1,2,4,6,3];

for (let i = 0, arrLength = arr.length; i < arrLength; i++) {
  if (arr[i] === magicNum) {
    console.log('Number Found!');
    continue;
  } else if (arr[i] > magicNum) {
    continue;
  } else if (arr[i] < magicNum) {
    // Stuck here
  }
}

2 回复 | 直到 6 年前

Nina Scholz 6 年前

可以采用迭代和递归的方法来查找子集和。

function getSubsets(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            result.push(t);
            return;
        }
        if (i === array.length) {
            return;
        }
        if (s + array[i] <= sum) { // shout circuit for positive numbers only
            fork(i + 1, s + array[i], t.concat(array[i]));
        }
        fork(i + 1, s, t);
    }

    var result = [];
    fork();
    return result;
}

console.log(getSubsets([10, 1, 2, 4, 6, 3], 9));

.as-console-wrapper { max-height: 100% !important; top: 0; }

为了只获取第一个子集,可以使用第一个找到的值数组退出递归。

function getFirstSubset(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            return  t;
        }
        if (i === array.length) {
            return;
        }
        return fork(i + 1, s + array[i], t.concat(array[i]))
            || fork(i + 1, s, t);
    }

    return fork();
}

console.log(getFirstSubset([10, 1, 2, 4, 6, 3], 9));

。作为控制台包装{最大高度:100%!重要;顶部:0;}

Sivcan Singh 6 年前

您可以参考以下内容来实现此目的: https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

实际上,您需要列出数组的所有子集,这些子集的位数之和等于给定的幻数。

编辑: 副本 find all subsets that sum to a particular value

function getSummingItems(a,t){
  return a.reduce((h,n) => Object.keys(h)
                                 .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
                                                                                      : m[k].map(sa => sa.concat(n)),m)
                                                                 :  m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]
    tgt = 9,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));