题意：给定一个二维数组，给定一个区间，返回该区间的二维数组中元素的和
思路：
- 遍历数组，计算每一个节点，到左上节点对应的矩阵中的点的和
- 对于每一个给定的区间矩阵，把该矩阵的四个点到左上点的区间，分割成四部分，结果＝整体－左部－上部＋左上部
思想：数组的遍历
复杂度：时间O（n2)，空间O(n2)
class NumMatrix {
int[][] temp;
int m;
int n;
public NumMatrix(int[][] matrix) {
m = matrix.length;
if(m == 0)
return;
n = matrix[0].length;
temp = new int[m][n];
if(n == 0)
return;
temp[0][0] = matrix[0][0];
for(int i=1;i<m;i++) {
temp[i][0] = temp[i-1][0] + matrix[i][0];
}
for(int j=1;j<n;j++) {
temp[0][j] = temp[0][j-1] + matrix[0][j];
}
for(int i=1;i<m;i++) {
for(int j=1;j<n;j++) {
temp[i][j] = matrix[i][j] - temp[i-1][j-1] + temp[i-1][j] + temp[i][j-1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if(row1 < 0 || col1 < 0 || row2 >= m || col2 >= n)
return 0;
int top = 0;
int left = 0;
int overlap = 0;
if(row1>0)
top = temp[row1-1][col2];
if(col1>0)
left = temp[row2][col1-1];
if(row1 > 0 && col1 > 0)
overlap = temp[row1-1][col1-1];
return temp[row2][col2] - top - left + overlap;
}
}
