304. 二维区域和检索 - 矩阵不可变
解题思路
image.png
和昨天的一样，利用 sum[i][j]表示 num[0][0]+... nums[i-1][j-1]的数值即可
具体可以参考 https://www.jianshu.com/p/e11b76a1eb4f
注意点
- 做预处理的时候，先按照行处理，再按照列处理。一定切记不可重复计算。
- 统计区域和 因为 sum[r][c] 被重复减掉了，需要加回来。
代码
type NumMatrix struct {
A [][]int
}
func Constructor(matrix [][]int) NumMatrix {
n := NumMatrix{}
if len(matrix)==0{
return n
}
r,c := len(matrix),len(matrix[0])
A := make([][]int,r+1)
A[0]=make([]int,c+1)
for i:=1;i<len(A);i++{
A[i]=make([]int,c+1)
for j:=1;j<len(A[i]);j++{
A[i][j]=A[i][j-1]+matrix[i-1][j-1]
}
}
for j:=1;j<len(A[0]);j++{
for i:=1;i<len(A);i++{
A[i][j]+=A[i-1][j]
}
}
n.A = A
return n
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
return this.A[row2+1][col2+1]+this.A[row1][col1]-this.A[row2+1][col1]-this.A[row1][col2+1]
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* param_1 := obj.SumRegion(row1,col1,row2,col2);
*/
