打卡第五十三天
2道中等题
题目：
思路：
代码：
class NumMatrix {vector<vector<int>> sum;
public:NumMatrix(vector<vector<int>> &matrix) {int m = matrix.size(), n = matrix[0].size();// 获取原矩阵的行数m和列数nsum.resize(m + 1, vector<int>(n + 1));// 初始化sum数组，大小为(m+1)×(n+1)，多一行一列便于计算for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 计算(i+1, j+1)位置的前缀和sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j]; // sum[i + 1][j] 左边矩形：第i+1行，0到j-1列// + sum[i][j + 1] 上边矩形：0到i-1行，第j+1列// - sum[i][j] 减去重复计算的左上角// + matrix[i][j] 加上当前元素值}}}int sumRegion(int r1, int c1, int r2, int c2) {//计算从(r1,c1)到(r2,c2)的矩形区域和return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1]; // sum[r2 + 1][c2 + 1] 目标矩形右下角// - sum[r2 + 1][c1] 减去左边部分// - sum[r1][c2 + 1] 减去上边部分// + sum[r1][c1] 加回重复减去的左上角}
};
耗时≈1.5小时 明天继续