304.md

Range Sum Query 2D - Immutable

题目

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example: Given 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

思路

part1 构造：
	对每一行
	matrix[i][j] += matrix[i][j-1]
par2 求解：
	求和(matrix[row][col2] - matrix[row][col1-1])(row 在区间[row1,row2])

代码

type NumMatrix struct {
    matrix [][]int 
}

func Constructor(matrix [][]int) NumMatrix {
    for r := 0; r < len(matrix); r++ {
        for c := 1; c < len(matrix[0]); c++ {
            matrix[r][c] += matrix[r][c-1]
        }
    } 
    var res NumMatrix
    res.matrix = matrix
    return res
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    res := 0
    //fmt.Println(this.matrix)
    for i := row1; i <= row2; i++ {
        if col1 != 0 {
            res += this.matrix[i][col2] - this.matrix[i][col1-1]
        } else {
            res += this.matrix[i][col2]
        }
    } 
    
    return res
}


/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */