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

糖逗

题目描述：

1. 给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
   
2. 
   
3. 子矩阵&#160;x1, y1, x2, y2&#160;是满足 x1 <= x <= x2&#160;且&#160;y1 <= y <= y2&#160;的所有单元&#160;matrix[x][y]&#160;的集合。
   
4. 
   
5. 如果&#160;(x1, y1, x2, y2) 和&#160;(x1', y1', x2', y2')&#160;两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
   
6. 
   
7. &#160;
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 
    
13. 输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
    
14. 输出：4
    
15. 解释：四个只含 0 的 1x1 子矩阵。
    
16. 示例 2：
    
17. 
    
18. 输入：matrix = [[1,-1],[-1,1]], target = 0
    
19. 输出：5
    
20. 解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
    
21. 示例 3：
    
22. 
    
23. 输入：matrix = [[904]], target = 0
    
24. 输出：0
    
25. &#160;
    
26. 
    
27. 提示：
    
28. 
    
29. 1 <= matrix.length <= 100
    
30. 1 <= matrix[0].length <= 100
    
31. -1000 <= matrix[i] <= 1000
    
32. -10^8 <= target <= 10^8
    
33. 
    
34. 来源：力扣（LeetCode）
    
35. 链接：https://leetcode.cn/problems/number-of-submatrices-that-sum-to-target
    
36. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
   
4.         int res = 0;
   
5.         //前缀和
   
6.         int len1 = matrix.size(), len2 = matrix[0].size();
   
7.         vector<vector<int> >sum(len1, vector<int>(len2, 0));
   
8.         //初始化
   
9.         sum[0][0] = matrix[0][0];
   
10.         for(int j = 1; j < len2; j++){
    
11.             sum[0][j] = sum[0][j-1] + matrix[0][j];
    
12.         }
    
13.         for(int i = 1; i < len1; i++){
    
14.             sum[i][0] = sum[i-1][0] + matrix[i][0];
    
15.         }
    
16.         //动态规划
    
17.         for(int i = 1; i < len1; i++){
    
18.             for(int j = 1; j < len2; j++){
    
19.                 sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + matrix[i][j];
    
20.             }
    
21.         }
    
22.         for(int x1 = 0; x1 < len1; x1++){
    
23.             for(int x2 = x1; x2 < len1; x2++){
    
24.                 for(int y1 = 0; y1 < len2; y1++){
    
25.                     for(int y2 = y1; y2 < len2; y2++){
    
26.                         int temp = 0;
    
27.                         if(x1 == 0 && y1 == 0){
    
28.                             temp = sum[x2][y2];
    
29.                         }else if(x1 == 0){
    
30.                             temp = sum[x2][y2] - sum[x2][y1-1];
    
31.                         }else if(y1 == 0){
    
32.                             temp = sum[x2][y2] - sum[x1-1][y2];
    
33.                         }else{
    
34.                             temp = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
    
35.                         }
    
36.                         if(temp == target){
    
37.                             res++;
    
38.                         }
    
39.                     }
    
40.                 }
    
41.             }
    
42.         }
    
43.         return res;
    
44.     }
    
45. };

复制代码

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

糖逗

相同思路的简便算法

1. class Solution {
   
2. public:
   
3.     int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
   
4.         int res = 0;
   
5.         //前缀和
   
6.         int len1 = matrix.size(), len2 = matrix[0].size();
   
7.         vector<vector<int> >sum(len1+1, vector<int>(len2+1, 0));
   
8.         //动态规划
   
9.         for(int i = 1; i <= len1; i++){
   
10.             for(int j = 1; j <= len2; j++){
    
11.                 sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + matrix[i-1][j-1];
    
12.             }
    
13.         }
    
14.         for(int x1 = 1; x1 <= len1; x1++){
    
15.             for(int x2 = x1; x2 <= len1; x2++){
    
16.                 for(int y1 = 1; y1 <= len2; y1++){
    
17.                     for(int y2 = y1; y2 <= len2; y2++){
    
18.                         int temp = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
    
19.                         if(temp == target){
    
20.                             res++;
    
21.                         }
    
22.                     }
    
23.                 }
    
24.             }
    
25.         }
    
26.         return res;
    
27.     }
    
28. };

复制代码