1074. Number of Submatrices That Sum to Target¶
题目信息¶
- 题号:
1074
- 难度:
Hard
- 主题:
整数矩阵、连续子矩阵、目标和计数
- 原题:
- 重点:
子矩阵必须由连续行和连续列形成且非空;相同内容出现在不同边界时按不同子矩阵分别计数
题目重述¶
给定整数矩阵 matrix 和整数 target。一个子矩阵由顶部行、底部行、左列和右列共同确定,包含这些边界之间的所有格子;行列范围都必须连续且至少包含一个格子。
请统计元素总和恰好等于 target 的非空子矩阵数量。即使两个子矩阵包含相同的数值,只要它们的边界位置不同,就应分别计数。
1 <= matrix.length, matrix[i].length <= 100,-1000 <= matrix[i][j] <= 1000,-10^8 <= target <= 10^8。
自建示例¶
横向、纵向和整矩阵都可能满足目标:
输入:matrix = [[1,-1],[-1,1]], target = 0
输出:5
解释:两行、两列以及整个 2 x 2 矩阵的元素和都为 0,共五个子矩阵。
矩阵只有一个格子:
输入:matrix = [[5]], target = 5
输出:1
解释:唯一非空子矩阵就是该格子本身,其元素和等于目标值。