前缀和 #

什么是前缀和 #

前缀和是一种常用的算法，用于快速计算数组中某个区间内元素的和 (快速计算数组取件内元素的和)

它可以将原本需要 O(n) 时间复杂度的区间求和操作优化到 O(1) 时间复杂度。

思路 #

具体方法是预处理出前缀和数组，即遍历一遍原数组，对于每个下标 i，将前 i 个数的和记录在一个新数组中。然后对于任意区间 [l, r] 的求和操作，只需要用前缀和数组计算出 sum[r] - sum[l - 1] 的差值即可得到该区间的和。

疑问 #

sum[r] - sum[l - 1] 的差值即可得到该区间的和 ？ 为什么？

原因：

假设我们有一个长度为 n 的数组 nums，它的前缀和数组为 sum。前缀和数组的定义为 sum[i] = nums[0] + nums[1] + ... + nums[i-1]，即表示 nums 数组前 i 个元素的和。

举个栗子：

对于数组 nums = [1, 2, 3, 4, 5]，它的前缀和数组为 sum = [0, 1, 3, 6, 10, 15]。其中，sum[0] 等于 0，表示数组 nums 前 0 个元素的和为 0；sum[1] 等于 nums[0]，表示数组 nums 前 1 个元素的和为 1；sum[2] 等于 nums[0] + nums[1]，表示数组 nums 前 2 个元素的和为 3；以此类推。

计算前缀和数组可以使用以下代码：

int sum[n+1];
sum[0] = 0;
for (int i = 1; i <= n; i++) {
    sum[i] = sum[i-1] + nums[i-1];
}

js语法为

    let sum = new Array(n+1); 
    sum[0] = 0; 
    for (let i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + nums[i-1]; 
    }

其中，sum[0] 初始化为 0，是为了方便后面的计算。

完整代码案列 #

// 定义一个数组
const nums = [3, 1, 4, 2, 5, 6];

// 定义一个新数组来存储前缀和
const prefixSum = [];

// 初始化前缀和数组的第一个元素为0，方便后面计算
prefixSum[0] = 0;

// 循环原数组，计算前缀和
for(let i = 1; i <= nums.length; i++) {
  // 前缀和数组中的第i个元素等于原数组中前i个数的和
  prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}

// 输出前缀和数组
console.log(prefixSum); // [0, 3, 4, 8, 10, 15, 21]