leetcode每日不做题
461. 汉明距离
852. 山脉数组的峰顶索引
374. 猜数字大小
278. 第一个错误的版本
474. 一和零
231. 2 的幂
342. 4的幂
1074. 元素和为目标值的子矩阵数量
477. 汉明距离总和
12. 整数转罗马数字
1190. 反转每对括号间的子串
692. 前K个高频单词
1738. 找出第 K 大的异或坐标值
1442. 形成两个异或相等数组的三元组数目
993. 二叉树的堂兄弟节点
421. 数组中两个数的最大异或值
13.罗马数字转整数
本文档使用 MrDoc 发布
-
+
首页
1074. 元素和为目标值的子矩阵数量
[力扣原题链接](https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/) ## 题目 给出矩阵`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. `1 <= matrix.length <= 100` 2. `1 <= matrix[0].length <= 100` 3. `-1000 <= matrix[i] <= 1000` 4. `-10^8 <= target <= 10^8` ## 思路 先求出二维数组的前缀和,再暴力遍历求出结果 ## 代码 语言:Java ``` class Solution { /** * 先求出二维数组的前缀和,再暴力遍历求出结果 * * @param matrix * @param target * @return */ public int numSubmatrixSumTarget(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int[][] prefixSum = new int[m+1][n+1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + matrix[i-1][j-1]; } } int result = 0; int sum; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= i; k++) { for (int l = 1; l <= j; l++) { sum = prefixSum[i][j] - prefixSum[k-1][j] - prefixSum[i][l-1] + prefixSum[k-1][l-1]; if(sum == target) { result++; } } } } } return result; } } ```
renyi567
2021年5月29日 18:13
转发文档
收藏文档
上一篇
下一篇
手机扫码
复制链接
手机扫一扫转发分享
复制链接
阅读量
次
本站总访问量
次
本站访客数
人次
Markdown文件
分享
链接
类型
密码
更新密码