NumberOfSubmatricesThatSumToTarget.cpp

// 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;
    }
};