C++刷leetcode（1074. 元素和为目标值的子矩阵数量）【前缀和】

糖逗

题目描述：

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。

 

示例 1：



输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。
示例 2：

输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
示例 3：

输入：matrix = [[904]], target = 0
输出：0
 

提示：

1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-submatrices-that-sum-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int res = 0;
        //前缀和
        int len1 = matrix.size(), len2 = matrix[0].size();
        vector<vector<int> >sum(len1, vector<int>(len2, 0));
        //初始化
        sum[0][0] = matrix[0][0];
        for(int j = 1; j < len2; j++){
            sum[0][j] = sum[0][j-1] + matrix[0][j];
        }
        for(int i = 1; i < len1; i++){
            sum[i][0] = sum[i-1][0] + matrix[i][0];
        }
        //动态规划
        for(int i = 1; i < len1; i++){
            for(int j = 1; j < len2; j++){
                sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + matrix[i][j];
            }
        }
        for(int x1 = 0; x1 < len1; x1++){
            for(int x2 = x1; x2 < len1; x2++){
                for(int y1 = 0; y1 < len2; y1++){
                    for(int y2 = y1; y2 < len2; y2++){
                        int temp = 0;
                        if(x1 == 0 && y1 == 0){
                            temp = sum[x2][y2];
                        }else if(x1 == 0){
                            temp = sum[x2][y2] - sum[x2][y1-1];
                        }else if(y1 == 0){
                            temp = sum[x2][y2] - sum[x1-1][y2];
                        }else{
                            temp = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
                        }
                        if(temp == target){
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
};

前缀和参考视频：https://www.bilibili.com/video/B ... arch-card.all.click

糖逗

相同思路的简便算法

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int res = 0;
        //前缀和
        int len1 = matrix.size(), len2 = matrix[0].size();
        vector<vector<int> >sum(len1+1, vector<int>(len2+1, 0));
        //动态规划
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        for(int x1 = 1; x1 <= len1; x1++){
            for(int x2 = x1; x2 <= len1; x2++){
                for(int y1 = 1; y1 <= len2; y1++){
                    for(int y2 = y1; y2 <= len2; y2++){
                        int temp = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
                        if(temp == target){
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
};