动态规划 - JavaScript数组元素部分和

在这个问题陈述中，我们的任务是计算数组所有元素的总和，并在每一步去除一个元素，并显示所有可能的子数组总和的结果数组。并使用Javascript功能实现此问题。

给定问题的逻辑

给定问题指出，我们必须计算每一步除一个元素之外的每个元素的总和。为了解决给定的问题，我们将定义一个数组作为输入，并返回一个数组作为输出，该数组通过在每次迭代中减去一个元素来计算元素的总和。

我们将使用for循环迭代数组的项目，并使用与之前相同的方法，通过消除当前元素来计算总和。然后将这些总和添加到新的结果数组中。在每个阶段，当前元素都会被更改。

算法

步骤1 − 在程序开始时，声明一个整数数组，该数组将用于计算每一步除一个元素之外的所有元素的总和。在我们的代码中，如果数组中有5个元素，那么我们将计算四个元素的总和。

步骤2 − 如果n是数组中存在的项目数，我们必须将n-1个项目的和存储在数组中。因此，为了存储总和，我们将创建一个总和数组。

步骤3 − 在Javascript中，我们有一种称为reduce的方法，用于通过逐一迭代元素来更新数组的所有值。因此，我们还将使用reduce方法来获取所有元素的总和。

步骤4 − 获取总和后，将其推入结果变量。

步骤5 − 现在启动for循环，并运行到数组的长度。

步骤6 − 在此阶段，我们将从数组中切片一个元素以获取n-1个项目的总和。

步骤7 − 在最后一步，将所有结果总和推入结果数组，并在控制台中获取输出。

Learn JavaScript in-depth with real-world projects through our JavaScript certification course. Enroll and become a certified expert to boost your career.

算法代码

Open Compiler
// array to calculate the part sum
const arr = [1, 2, 3, 4, 5];

// resultant array 
const sumArray = (arr = []) => arr.reduce((a, b) => a + b, 0);
const sumWithoutOne = (arr = []) => {
   const result = [sumArray(arr)];
   for (let i = 0; i < arr.length; i++) {
      const sum = sumArray(arr.slice(0, i).concat(arr.slice(i + 1)));
      result.push(sum);
   }
   return result;
};
console.log(sumWithoutOne(arr));

复杂度

我们可以在代码中看到，我们使用reduce方法，它需要O(n)时间来执行。另一个函数sumWithoutOne使用for循环和slice方法，它也需要O(n)时间，但slice方法被调用n次，因为它在for循环中，所以总时间复杂度将为O(n^2)。空间复杂度为O(n)，其中n是新数组中总和的个数。

结论性说明

我们在上面的算法中看到了如何获取数组一部分的总和。如果一个数组有n个元素，我们通过每一步从数组中删除一个元素并创建一个新的数组来计算n-1个元素的总和，该数组包含n-1个项目的总和。因此，这段代码的时间复杂度为O(n^2)，空间复杂度为O(n)。

更新于：2023年5月18日

381 次浏览

启动您的职业生涯

完成课程后获得认证

开始
广告