力扣 304. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。 实现 NumMatrix 类：
- NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
- int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1)、右下角(row2,col2) 所描述的子矩阵的元素 总和 。
方案一：使用前缀和配合无序映射。
type NumMatrix struct {
preSum [][]int // 二维前缀和数组
}
func Constructor(matrix [][]int) NumMatrix {
// 构建二维数组计算前缀和，下标从 1 开始可以减少边界判断，所以前缀和数组长度较原数组大 1
m , n := len(matrix), len(matrix[0])
preSum := make([][]int, m + 1)
for i := range preSum {
preSum[i] = make([]int, n + 1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
// 计算前缀和
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] -
preSum[i - 1][j - 1] + matrix[i - 1][j - 1]
}
}
return NumMatrix{
preSum: preSum,
}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
// 因为计算前缀和时下标加了一，所以 row1, col1 处的前缀和其实是 preSum[row1 + 1][col1 + 1]
return this.preSum[row2 + 1][col2 + 1] -
this.preSum[row1][col2 + 1] - this.preSum[row2 + 1][col1] +
this.preSum[row1][col1]
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* param_1 := obj.SumRegion(row1,col1,row2,col2);
*/
- 时间复杂度：O(m * n)，构造函数在运行时需要遍历所有元素，所以时间复杂度在 O(m * n)，而 SumRegion 函数不涉及复杂操作，时间复杂度在 O(1)。
- 空间复杂度：O(m * n)，是因为使用了长度为 (m+1) * (n + 1) 的二维数组保存了前缀和，所以空间复杂度为 O(m * n)。