JavaScript中无法表示为子数组之和的最小正值

我们有一个排序的正整数数组，如下所示：

const arr = [1, 3, 6, 10, 11, 15];

我们需要编写一个函数，例如 findSmallest()，它接受这样一个数组并返回不能表示为该原始数组的某些子数组之和的最小正整数。

例如：

对于上面写的这个数组，2 是不能通过对这个原始数组的任何子数组求和得到的最小正整数。所以，现在让我们为这个函数编写代码。由于数组已排序，我们可以在线性时间内解决这个问题。我们最初认为所需数字是 1，因为 1 是它可以取的最小值。我们将遍历数组并将相应的元素添加到所需数字中。

如果在任何迭代中，相应的数字大于所需数字，则意味着我们找到了所需数字，否则我们将继续迭代。

示例

const arr = [1, 3, 6, 10, 11, 15];
const findSmallest = arr => {
   let res = 1;
   for(let ind = 0; ind < arr.length && arr[ind] <= res; ind++){
      res += arr[ind];
   }
   return res;
};
console.log(findSmallest(arr));

输出

控制台中的输出将是：

2

更新于：2020年8月31日

91 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告