Title:
The matrix and target value are given, and the number of non empty submatrixes whose sum of elements is equal to the target value is returned.

Thinking:
This topic is similar to 363. Rectangular area does not exceed the maximum sum of K, 560. Sum is a subarray of K, and 2. Sum of two numbers. You can do these questions first, and then come back to solve this problem.
If you have the prefix and knowledge, you may think of using the two-dimensional prefix sum to search the array. How to realize it?
First of all, the code to implement the two-dimensional prefix sum with an array is as follows:

 sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];

Based on the implementation of prefix sum, we need to get the sum of each sub matrix. How can we do that? This can refer to the following code. Every time we take i j as the label of the lower right corner of the current maximum matrix, the submatrix contained in the matrix must be at the upper left of it. Considering that we add one element every time in the process of ij cycle, the new submatrix for the maximum envelope matrix only contains all the matrices at the new ij coordinates, and other matrices have been retrieved in the previous traversal. Therefore, in each envelope matrix, we add P, Q, where p represents the cut-off line in the x direction and Q represents the cut-off line in the y direction. Note that it's equivalent to p starting from 0 to i-1, Q starting from j-1 to 0, or for better understanding. On the other hand, P starts from i-1k, and Q starts from j-1 to 0 every time. Then these two cut-off lines help to filter out all new subsets including the lower right corner ~ ~ the following code p q=1. Add 1, then reduce 1!

 for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = 1; p <= i; p++) {
                    for (int q = 1; q <= j; q++) {
                        if (sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1] == t) ans++;
                    }
                }
            }
        }

To sum up, the code of violence prefix and search is as follows:

class Solution {
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int n = mat.length, m = mat[0].length;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = 1; p <= i; p++) {
                    for (int q = 1; q <= j; q++) {
                        if (sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1] == t) ans++;
                    }
                }
            }
        }
        return ans;
    }
}

However, this method will time out, and the maximum time complexity is o(m2n2), although it is not. But not yet.
Furthermore, the official solution of Leetcode gives the method of prefix and + hash table to optimize the time complexity. The basic idea is that we enumerate the upper boundary and the lower boundary. The total boundary length is m, and they can overlap. The total number of cycles is m+m-1... + 1, and the total complexity is the square of M. Suppose there's only one column, and that's all the submatrix. How to enumerate all combinations when adding columns.
We know that in a certain case of the above loop, I know that a row is the upper boundary, and there are many lower boundaries. I use a one-dimensional array of sum, with the same dimension and column number, to record the column accumulation sum of a lower boundary under the current upper boundary, and record each column accumulation in the space corresponding to sum. Each time a lower boundary is recorded, a set of data is obtained, and then the sum is processed and searched.
We know that if column = 3, there are 6 subsets in the total combination, and we need to find 6 subsets by violence method. Is there a faster way? Can we do it with three searches. In fact, we can. We know the target value of the title. Therefore, when we traverse each element of sum, we calculate its prefix sum, and then store it in the hash table. We notice that every time we traverse to the accumulated value, the subset in the middle comes from the accumulated value pre minus the accumulated value pre of a certain time. If a value in the middle is equal to target, pre past + target=pre present, so once pre target appears in the hash table, it means that there is a subset whose sum is equal to target. Moreover, because there is a negative number, the number of subsets is not necessarily 1, so add the number of pre-k. Moreover, the accumulated value must contain the subset of the current matrix, so it is different from the previous one and needs to be superimposed. Note that mp[0]=1. Considering that we only record the prefix and prefix in the hash table every time, pre-K is the retrieval of the previous element, but if we want to retrieve the current overall element, we can't do it, that is, when pre-K is equal to 0, we need to add 1 to it!

class Solution {
private:
    int subarraySum(vector<int> &nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto &x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }

public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
        int ans = 0;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) { // Enumeration upper boundary
            vector<int> sum(n);
            for (int j = i; j < m; ++j) { // Enumerating lower bounds
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // Update the elements and values of each column
                }
                ans += subarraySum(sum, target);
            }
        }
        return ans;
    }
};