二刷 07/2022
Version #2 Prefix Sum by Row
比之前的方法少了一个dimension，因为用到了hashmap记录了之前prefixsum的值
Time O(M^2N)
Space O(MN)
Runtime: 276 ms, faster than 45.16% of Java online submissions for Number of Submatrices That Sum to Target.
Memory Usage: 117.6 MB, less than 37.22% of Java online submissions for Number of Submatrices That Sum to Target.
class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int[][] prefixSums = new int[rows][cols + 1];
for (int y = 0; y < rows; y++) {
for (int x = 1; x <= cols; x++) {
prefixSums[y][x] = prefixSums[y][x - 1] + matrix[y][x - 1];
}
}
int result = 0;
// prefixSum[i] - sum from element [0, i - 1]
// prefixSum[end] - prefixSum[start] - sum [start, end)
for (int start = 0; start < cols; start++) {
for (int end = start + 1; end <= cols; end++) {
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
map.put(0, 1);
for (int y = 0; y < rows; y++) {
sum += prefixSums[y][end] - prefixSums[y][start];
// sum - prevSum = target
result += map.getOrDefault(sum - target, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
}
return result;
}
}
一刷 07/2022
Version #1 Square Prefix Sum Brute Force
Time O(M^2N^2)
Space O(MN)
Runtime: 351 ms, faster than 18.36% of Java online submissions for Number of Submatrices That Sum to Target.
Memory Usage: 45.8 MB, less than 76.92% of Java online submissions for Number of Submatrices That Sum to Target.
class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
long[][] sums = new long[rows + 1][cols + 1];
for (int y = 0; y <= rows; y++) {
for (int x = 0; x <= cols; x++) {
if (y == 0 || x == 0) {
sums[y][x] = 0;
continue;
}
sums[y][x] = matrix[y - 1][x - 1] + sums[y - 1][x] + sums[y][x - 1] - sums[y - 1][x - 1];
}
}
int result = 0;
// (top,left) (top,right)
// (down,left) (down,right)
for (int top = 0; top < rows; top++) {
for (int down = top + 1; down <= rows; down++) {
for (int left = 0; left < cols; left++) {
for (int right = left + 1; right <= cols; right++) {
if (sums[down][right] - sums[top][right] - sums[down][left] + sums[top][left] == target) {
result++;
}
}
}
}
}
return result;
}
}
