前缀和问题

什么是前缀和？

一维前缀和

假设x为一数组，y为数组x的前缀和数组，则x和y满足如下关系:

y0 = x0 , y1 =x0 +  x1 , y2 =x0 +  x1 +  x2,yn =x0 +  x1 +  x2 + ... + xny_{0\ }=\ x_0\ ,\ y_1\ =x_0\ +\ \ x_1\ ,\ y_2\ =x_0\ +\ \ x_1\ +\ \ x_2 , y_n\ = x_0\ +\ \ x_1\ +\ \ x_2 \ +\ ... \ +\ x_n

二维前缀和

假设x为二维数组，y为数组x的二维前缀和数组，则x和y满足如下关系:

y0,0=x0,0,y0,1=x0,0+a0,1,y1,0=x0,0+x1,0,y1,1=x0,0+x0,1+x1,0+x1,1…y_{0,0}=x_{0,0}, y_{0,1}=x_{0,0}+a_{0,1}, y_{1,0}=x_{0,0}+x_{1,0}, y_{1,1}=x_{0,0}+x_{0,1}+x_{1,0}+x_{1,1}\dots

如上图，右侧二位前缀和数组标红元素 y2,2y_{2, 2} 的值等于左侧二维数组标红区域元素之和

如何计算

一维前缀和

yn=yn−1+xny_n=y_{n-1}+x_n

代码实现

for (let i = 0; i < n; i++) {
    if (i === 0) {
        y[i] = x[i]
    } else {
        y[i] = y[i - 1] + x[i]
    }
}

二位前缀和

yi,j=yi−1,j+yi,j−1−yi−1,j−1+xi,jy_{i, j}=y_{i-1,j}+y_{i,j-1}-y_{i-1,j-1}+x_{i,j}

代码实现

// n * m
for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (i === 0 && j === 0) {
            y[j][i] = x[j][i]
        } else if (j === 0) {
            y[j][i] = y[j][i - 1] + x[j][i]  // 一维数组前缀和
        } else if (i === 0) {
            y[j][i] = y[j - 1][i] + x[j][i]  // 一维数组前缀和
        } else {
            y[j][i] = y[j - 1][i] + y[j][i - 1] - y[j - 1][i - 1] + x[j][i]
        }
    }
}

前缀和应用

参考链接

  • 连续子数组求和问题

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和

let preSum = [arr[0]], res = 0, n = arr.length;
for (let i = 1; i < n; i++) {
    preSum[i] = preSum[i - 1] + arr[i]
}
preSum.unshift(0)
console.log('preSum', preSum)

for (let i = 0; i < n; i++) {
    for (let j = 1; i + j - 1 < n; j += 2) {
        // console.log('ele', arr.slice(i, i + j))
        // i = 0的时候，preSum[0]是人为补上的
        // S(i + j) - S(i)是{x(i), x(i + 1), x(i + 2), ..., x(i + j)的和
        res += preSum[i + j] - preSum[i]  
    }
}
return res;

Previous单链表问题Next移除有序数组中重复项

Last updated