Given a matrix&nbsp;and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 &lt;= x &lt;= x2 and y1 &lt;= y &lt;= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate&nbsp;that is different: for example, if x1 != x1'.

&nbsp;
Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.


Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.


Example 3:

Input: matrix = [[904]], target = 0
Output: 0


&nbsp;
Constraints:


	1 &lt;= matrix.length &lt;= 100
	1 &lt;= matrix[0].length &lt;= 100
	-1000 &lt;= matrix[i] &lt;= 1000
	-10^8 &lt;= target &lt;= 10^8


class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        matrix_sums = [[0 for _ in range(n)] for _ in range(m)]
        
        # Calculate all the submatrices sum with the transition formula we found
        for row in range(m):
            for col in range(n):
                # first cell
                if row == 0 and col == 0:
                    matrix_sums[row][col] = matrix[row][col]
                # Rows and columns are like prefix sums, without intersection
                elif row == 0:
                    matrix_sums[row][col] = matrix[row][col] + matrix_sums[row][col-1]
                elif col == 0:
                    matrix_sums[row][col] = matrix[row][col] + matrix_sums[row-1][col]
                
                # current sum is the sum of the matrix above, to the left and subtract the intersection
                else:
                    matrix_sums[row][col] = matrix[row][col] \
                    + (matrix_sums[row][col-1]) \
                    + (matrix_sums[row-1][col]) \
                    - (matrix_sums[row-1][col-1])

                
        ans = 0
        # Generate all submatrices
        for y1 in range(m):
            for x1 in range(n):
                for y2 in range(y1, m):
                    for x2 in range(x1, n):
                        # calculate sum in O(1)
                        submatrix_total = matrix_sums[y2][x2] \
                        - (matrix_sums[y2][x1-1] if x1-1 >= 0 else 0) \
                        - (matrix_sums[y1-1][x2] if y1-1 >= 0 else 0) \
                        + (matrix_sums[y1-1][x1-1] if y1-1 >= 0 and x1-1 >= 0 else 0)
                        
                        if submatrix_total == target:
                            ans += 1
        return ans
class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;

    int[] summedArray = new int[n];
    int ans = 0;
    for(int i = 0; i < m; i++){ //starting row
        Arrays.fill(summedArray, 0);
        for(int j = i; j < m; j++){ //ending row
            for(int k = 0; k < n; k++){ // column
                summedArray[k] += matrix[j][k];
            }
            ans += subarraySum(summedArray, target);
        }
    }
    return ans;
}

 public int subarraySum(int[] nums, int k) {
    //map<sum, freq>
    Map<Integer, Integer> map = new HashMap<>();
    int count = 0;
    map.put(0,1);
    int sum = 0;
    for(int num : nums){
        sum += num;
        int diff = sum - k;
        if(map.containsKey(diff)){
            count += map.get(diff);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}
}
class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int n=matrix.size(),m=matrix[0].size(),count=0;
        vector<vector<int>>temp(n+1,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                temp[i+1][j]=temp[i][j]+matrix[i][j];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<=n;j++){
                for(int k=0;k<m;k++){
                    int sum=0;
                    for(int l=k;l<m;l++){
                        sum+=temp[j][l]-temp[i][l];
                        if(sum==target){
                            // cout<<j<<" "<<i<<" "<<k<<endl;
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
};
var numSubmatrixSumTarget = function(matrix, target) {
    let result = 0;
    
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 1; j < matrix[0].length; j++) {
            matrix[i][j] = matrix[i][j] + matrix[i][j-1]
        }
    }
    
    for (let i = 0; i < matrix[0].length; i++) {
        for (let j = i; j < matrix[0].length; j++) {
            let dict = {};
            let cur = 0;
            dict[0] = 1;
            
            for (let k = 0; k < matrix.length; k++) {
                cur += matrix[k][j] - ((i > 0)?(matrix[k][i - 1]):0);
                result += ((dict[cur - target] == undefined)?0:dict[cur - target]);
                dict[cur] = ((dict[cur] == undefined)?0:dict[cur])+1;
            } 
        }
    }
    
    return result;
};
Number of Submatrices That Sum to Target