行业网站推广方案,潍坊住房和城乡建设厅网站,商城网站网站开发,给网站做路由给出矩阵 matrix 和目标值 target#xff0c;返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 x x2 且 y1 y y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐…给出矩阵 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
解题思路
遍历所有可以可选的上下边界[i,j]。
在上下界已经确定的情况下维护前缀和数组cnt[i],代表第i列所有元素的累加和。从第一列开始不断累加累加到cur当中cur代表上下界确定的情况下累加起来的前n列使用map记录下前n列累加和为k1的情况当遍历到前n2列时累加和为k2时若满足k2-k1target即说明子矩阵[n,n2]的和为target。
代码
func numSubmatrixSumTarget(matrix [][]int, target int) (res int) {for i : 0; i len(matrix); i {col : make([]int, len(matrix[0]))for j : i; j len(matrix); j {for z : 0; z len(matrix[0]); z {col[z] matrix[j][z]}func() {m : make(map[int]int)m[0] 1cur : 0for i : 0; i len(matrix[0]); i {cur col[i]i2, has : m[cur-target]if has {res i2}m[cur]}}()}}return}
