Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int r = matrix.size(), c = matrix[0].size();
vector<vector<int>> pref(matrix.size() + 1, vector<int> (matrix[0].size() + 1, 0));
for(int i = 1; i < r + 1; i++)
{
for(int j = 1; j < c + 1; j++)
{
pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + matrix[i-1][j-1];
}
}
int count = 0, currSum;
unordered_map<int, int> m;
for(int r1 = 1; r1 < r + 1; r1++)
{
for(int r2 = r1; r2 < r +1; r2++)
{
m.clear();
m[0]++;
for(int col = 1; col < c + 1; col++)
{
currSum = pref[r2][col] - pref[r1 - 1][col];
count += m[currSum - target];
m[currSum]++;
}
}
}
return count;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.