Matrix Block Sum
给一个2d数组和一个k, 求k的范围内的和. 这个题和range sum的那个一样的结构, 只是query部分稍加改动. 附上一个答案里很简练的做法.
class Solution {
public int[][] matrixBlockSum(int[][] mat, int K) {
int m = mat.length, n = mat[0].length;
int[][] sum = new int[m + 1][n + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];
int[][] ans = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
int r1 = Math.max(0, i - K);
int c1 = Math.max(0, j - K);
int r2 = Math.min(m, i + K + 1);
int c2 = Math.min(n, j + K + 1);
ans[i][j] = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
}
return ans;
}
}