leetcode 3070. 元素和小于等于 k 的子矩阵的数目 中等

给你一个下标从0开始的整数矩阵grid和一个整数k。返回包含grid左上角元素、元素和小于或等于k的子矩阵的数目。示例 1输入grid [[7,6,3],[6,6,1]], k 18输出4解释如上图所示只有 4 个子矩阵满足包含 grid 的左上角元素并且元素和小于或等于 18 。示例 2输入grid [[7,2,9],[1,5,0],[2,6,6]], k 20输出6解释如上图所示只有 6 个子矩阵满足包含 grid 的左上角元素并且元素和小于或等于 20 。提示m grid.lengthn grid[i].length1 n, m 10000 grid[i][j] 10001 k 10^9分析求出二维前缀和统计有多少个和的值小于等于 k 即可。int countSubmatrices(int** grid, int gridSize, int* gridColSize, int k) { int ngridSize,mgridColSize[0],ans0,sum[n5][m5]; if(grid[0][0]k)return 0; else ans1; sum[0][0]grid[0][0]; for(int i1;in;i) { sum[i][0]sum[i-1][0]grid[i][0]; if(sum[i][0]k)ans; } for(int i1;im;i) { sum[0][i]sum[0][i-1]grid[0][i]; if(sum[0][i]k)ans; } for(int i1;in;i) for(int j1;jm;j) { sum[i][j]grid[i][j]-sum[i-1][j-1]sum[i-1][j]sum[i][j-1]; if(sum[i][j]k)ans; } return ans; }