前缀和问题
什么是前缀和?
一维前缀和
假设x
为一数组,y
为数组x
的前缀和数组,则x
和y
满足如下关系:
二维前缀和
假设x
为二维数组,y
为数组x
的二维前缀和数组,则x
和y
满足如下关系:

如上图,右侧二位前缀和数组标红元素 的值等于左侧二维数组标红区域元素之和
如何计算
一维前缀和
代码实现
for (let i = 0; i < n; i++) {
if (i === 0) {
y[i] = x[i]
} else {
y[i] = y[i - 1] + x[i]
}
}
二位前缀和
代码实现
// 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;
Last updated
Was this helpful?