什么是前缀和
前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时间复杂度。
什么是一维前缀和?
一维前缀和的公式:sum[i] = sum[i-1] + arr[i]
; sum
是前缀和数组, arr
是内容数组。拥有前缀和数组后, 我们可以在O(1)
的时间复杂度内求出区间和。
[i, j]
的区间和公式: interval [i, j] = sum[j] - sum[i - 1]
和为K的子数组
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
- 数组的长度为 [1, 20,000]。
- 数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。
思路1: 使用前缀和
首先遍历数组构建前缀和数组,在拥有前缀和数组后,通过双层循环计算数组中每一个子项与之前的子项之间的区间和(子数组的和)。此时的时间复杂度为O(n^2)。
/** * @param {number[]} nums * @param {number} k * @return {number} */
var subarraySum = function(nums, k) {
const pre = []
let count = 0
// 构建前缀和数组
for (let i = 0; i < nums.length; i++) {
const a = nums[i]
const b = pre[i - 1] === undefined ? 0 : pre[i - 1]
pre[i] = a + b
}
// 使用前缀和,可以快速获得区间和
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j <= i; j++) {
// 计算区间和,查找到满足条件的区间和,count加一
let intervalSum;
if (j === 0) {
intervalSum = pre[i]
} else if (j === i) {
intervalSum = nums[i]
} else {
intervalSum = pre[i] - pre[j - 1]
}
if (intervalSum === k) {
count += 1
}
}
}
return count
};
思路1(优化): 使用前缀和 + 哈希
如果只使用前缀和, 时间复杂度还是太高了。无法通过全部的测试用例,会超时。下面使用哈希表降低时间复杂度。
说实话使用前缀和加哈希的解法,我思考了很久才理解思路。下面我来解释一下
我们之前知道区间和的公式等于k = sum[j] - sum[i - 1]
, 我们通过简单的移项可以得出这个公式sum[i - 1] = sum[j] - k
。我们在遍历nums
时,可以获得当前的前缀和,当前的前缀和减去k,可以得到我们需要找的另一个前缀和的大小,如果hash之中有记录,我们只需要获取hash中的记录,就可以知道有多少区间和等于k了。
/** * @param {number[]} nums * @param {number} k * @return {number} */
var subarraySum = function(nums, k) {
let count = 0
let preSum = 0
let hash = {}
for (let i = 0; i < nums.length; i++) {
preSum += nums[i]
const key = preSum - k
if (hash[key]) {
count += hash[key]
}
if (preSum === k) {
count += 1
}
// 记录前缀和出现的次数
if (!hash[preSum]) {
hash[preSum] = 1
} else {
hash[preSum] += 1
}
}
return count
};
什么是二维前缀和?
什么是二维前缀和?二维前缀和其实就是二维数组的前缀和,二维前缀和的计算过程如下:
const arr = [
[1, 1, 1],
[1, 1, 1],
[1, 1, 1],
]
// 对于 i = 0 j = 0 preSum[0, 0] = arr[0, 0]
// 对于 i = 0 preSum[0, j] = preSum[0, j-1] + arr[0, j]
// 对于 j = 0 preSum[i, 0] = preSum[i-1, 0] + arr[i, 0]
// 其他情况 j != 0 i != 0 preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + src[i][j] - preSum[i - 1][j - 1];
const preSum = [[], [], []]
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[0].length; j++) {
if (i == 0 && j == 0) {
preSum[i][j] = arr[i][j]
} else if (i == 0) {
preSum[i][j] = preSum[i][j - 1] + arr[i][j]
} else if (j == 0) {
preSum[i][j] = preSum[i - 1][j] + arr[i][j]
} else {
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + arr[i][j] - preSum[i - 1][j - 1]
}
}
}
// preSum
[
[1, 2, 3],
[2, 4, 6],
[3, 6, 9]
]
二维区域和检索 – 矩阵不可变
本题可以看作求二维数组的区间和
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。
上图子矩阵左上角 (row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),该子矩形内元素的总和为 8。
示例:
给定 matrix = [ [3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
思路
首先求得二维数组对应的二维前缀和数组。接下来看下图:
如果想求得A顶点到B定点的区域和,我们可以使用如下的办法
sumRegion(A,B) = preSum(O,B) - preSum(O,C) - preSum(O,D) + preSum(O,E)
递推公式:
sumRegion(row2, col2, row1, col1) = preSum[row2][col2] − preSum[row2][col1−1] − preSum[row1−1][col2] + preSum[row1−1][col1−1]
我们需要额外考虑当row2,col2,row1,col1等于0时的情况,我们额外在前缀和的一条边,一条列,这样可以避免大量的边界条件判断。
此时的公式变为了:
sumRegion(row2, col2, row1, col1) = preSum[row2 + 1][col2 + 1] − preSum[row2 + 1][col1] − preSum[row1][col2 + 1] + preSum[row1][col1]
/** * @param {number[][]} matrix */
var NumMatrix = function(matrix) {
// 原矩阵
this.matrix = matrix
// 前缀和矩阵
this.preSum = null
if (matrix.length === 0 || matrix[0].length === 0) {
return
}
// 构建前缀和矩阵
this.preSum = []
for (let i = 0; i < this.matrix.length; i++) {
this.preSum.push([])
}
for (let i = 0; i < this.matrix.length; i++) {
for (let j = 0; j < this.matrix[0].length; j++) {
if (i == 0 && j == 0) {
this.preSum[i][j] = this.matrix[i][j]
} else if (i == 0) {
this.preSum[i][j] = this.preSum[i][j - 1] + this.matrix[i][j]
} else if (j == 0) {
this.preSum[i][j] = this.preSum[i - 1][j] + this.matrix[i][j]
} else {
this.preSum[i][j] = this.preSum[i - 1][j] + this.preSum[i][j - 1] + this.matrix[i][j] - this.preSum[i - 1][j - 1]
}
}
}
// 前缀和矩阵额外添加一行一列
// 添加一列
for (let i = 0; i < this.preSum.length; i++) {
this.preSum[i].unshift(0)
}
// 添加一行
this.preSum.unshift(new Array(this.preSum[0].length).fill(0))
};
/** * @param {number} row1 * @param {number} col1 * @param {number} row2 * @param {number} col2 * @return {number} */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
if (this.preSum) {
return this.preSum[row2 + 1][col2 + 1] + this.preSum[row1][col1] - this.preSum[row2 + 1][col1] - this.preSum[row1][col2 + 1]
}
return null
};
/** * Your NumMatrix object will be instantiated and called as such: * var obj = new NumMatrix(matrix) * var param_1 = obj.sumRegion(row1,col1,row2,col2) */
今天的文章什么是前缀和?分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/20415.html