#1074. Number of Submatrices That Sum to Target
function numSubmatrixSumTarget(matrix, target) {
const rows = matrix.length;
const cols = matrix[0].length;
let count = 0;
// Compute prefix sum for each row
const prefixSum = [];
for (let row = 0; row < rows; row++) {
prefixSum[row] = [];
prefixSum[row][0] = matrix[row][0];
for (let col = 1; col < cols; col++) {
prefixSum[row][col] = prefixSum[row][col - 1] + matrix[row][col];
}
}
for (let startCol = 0; startCol < cols; startCol++) {
for (let endCol = startCol; endCol < cols; endCol++) {
const seen = new Map();
let curSum = 0;
seen.set(0, 1);
for (let row = 0; row < rows; row++) {
curSum += prefixSum[row][endCol] - (startCol > 0 ? prefixSum[row][startCol - 1] : 0);
if (seen.has(curSum - target)) {
count += seen.get(curSum - target);
}
seen.set(curSum, (seen.get(curSum) || 0) + 1);
}
}
}
return count;
}
I don't understand this solution.
ย