代码之家 › 专栏 › 技术社区 › 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));

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前