1074. Number of Submatrices That Sum to Target
https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description
給你一個二維陣列表示的矩陣和一個 target,找出這個矩陣的所有子矩陣全部元素相加
為0的有幾個。
https://assets.leetcode.com/uploads/2020/09/02/mate1.jpg
思路:
1.遍歷所有的矩陣座標,以該座標為起點往右下角窮舉所有產生的子矩陣並檢查和是否
等於 target,舉例來說以 (0,0) 為起點的話求的子矩陣順序會是
[0]
[0,1]
[0,1,0]
[0
1]
[0,1
1,1]
[0,1,0
1,1,1]
[0
1
0]
[0,1
1,1
0,1]
[0,1,0
1,1,1
0,1,0]
可以看出就是在找:第i列到第j行的和 + 第i-1列到第j行的和 + 第i-2列到第j行的和
+ .... + 第0列到第j行的和
判斷所有算出來的和是不是和target相等即可。
Java Code: