- 題目描述
- 解題思路
- 代碼
- 複雜度分析
題目描述
題目連結
給出矩陣 matrix 和目标值 target，傳回元素總和等于目标值的非空子矩陣的數量。
子矩陣 x1, y1, x2, y2 是滿足 x1 <= x <= x2 且 y1 <= y <= y2 的所有單元 matrixx 的集合。
如果 (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 子矩陣。 複制
提示：
1 <= matrix.length <= 300
1 <= matrix[0].length <= 300
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8 複制
解題思路
根據題目，肯定要求從 (x1,y1,x2,y2) 的和，那麼最好能将從 (0,0,x,y) 的矩陣和計算出來，否則複雜度會很高。
可以設 sumi 為矩陣 matrix0 到 matrixi 的元素和，那麼 sumi 的推導公式為：
- i == 0 && j == 0 時，sumi = matrixi
- i == 0 && j != 0 時，sumi = matrixi + sumi
- i != 0 && j == 0 時，sumi = matrixi + sumi - 1
- i != 0 && j != 0 時，sumi = matrixi - sumi - 1 + sumi - 1 + sumi
解釋一下最後一個，對于 (0,0,i,j) 這個矩陣，在已知 (0,0,i-1,j-1) 的情況下，需要加上第 j 列和第 i 行，不過這 2 個加入的話，就會把 (0,0,i-1,j-1) 多計算一遍，減去即可。
20210220105354
接下來就是在計算出 suni 之後，對于每行周遊 0~i，對于每列周遊 0~j，分别計算每個矩陣。
代碼
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int row = matrix.length, col = matrix[0].length;
int[][] sum = new int[row][col];
int ans = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 && j == 0) {
sum[i][j] = matrix[i][j];
} else if (i == 0) {
sum[i][j] = matrix[i][j] + sum[i][j - 1];
} else if (j == 0) {
sum[i][j] = matrix[i][j] + sum[i - 1][j];
} else {
sum[i][j] = matrix[i][j] - sum[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1];
}
for (int k = 0; k <= i; k++) {
for (int l = 0; l <= j; l++) {
int main = (k != 0 && l != 0) ? sum[k - 1][l - 1] : 0;
int left = k != 0 ? sum[i - 1][l] : 0;
int up = l != 0 ? sum[k][j - 1] : 0;
if (sum[i][j] - left - up + main == target) {
ans++;
}
}
}
}
}
return ans;
} 複制
複雜度分析
時間複雜度：$O(row^2 * col^2)$
空間複雜度：因為建立了一個數組矩陣 sum，複雜度為 $O(row*col)$