网站开发长期合作,wordpress切换语言包,开创者wordpress素材,安全又舒适的避孕方法有哪些Every day a Leetcode
题目来源#xff1a;3070. 元素和小于等于 k 的子矩阵的数目
解法1#xff1a;二维前缀和
二维前缀和的模板题。
代码#xff1a;
/** lc appleetcode.cn id3070 langcpp** [3070] 元素和小于等于 k 的子矩阵的数目*/// lc codestart// 二维前缀和…Every day a Leetcode
题目来源3070. 元素和小于等于 k 的子矩阵的数目
解法1二维前缀和
二维前缀和的模板题。
代码
/** lc appleetcode.cn id3070 langcpp** [3070] 元素和小于等于 k 的子矩阵的数目*/// lc codestart// 二维前缀和class Solution
{
public:int countSubmatrices(vectorvectorint grid, int k){if (grid.empty())return 0;if (grid[0][0] k)return 0;int m grid.size(), n m ? grid[0].size() : 0;// sum[i 1][j 1] 表示以 grid[0][0] 为左上角// 以 grid[i][j] 为右下角的子矩阵的元素和 vectorvectorint sum(m 1, vectorint(n 1, 0));int count 0;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] grid[i][j];if (sum[i 1][j 1] k)count;}return count;}
};
// lc codeend结果 复杂度分析
时间复杂度O(mn)其中 m 和 n 分别为二维数组 grid 的行数和列数。
空间复杂度O(mn)其中 m 和 n 分别为二维数组 grid 的行数和列数。
