Concise Easy to Understand Intuition and Code
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nFor each pair of columns (i, j) from index i to j inclusive:\n\nCreate a 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFor each pair of columns (i, j) from index i to j inclusive:\n\nCreate a hashmap (freq) to store the frequency of cumulative sums.\nInitialize the cumulative sum sum as 0.\nInitialize cumuColSum to track the cumulative column sums for each row, starting from column i to column j.\nTraverse each row (k) from 0 to n-1:\n\nUpdate the cumuColSum[k] with the current value in matrix[k][j] plus the previous cumulative sum value.\nIncrement the frequency of the current cumulative sum sum in the freq map.\nUpdate sum by adding the current cumuColSum[k].\nAt each step in row traversal:\n\nIncrement the count by the frequency of (sum - target) in the freq map. This implies that there are freq[sum - target] submatrices that sum to the target value ending at the current row.\nThe count is the final result representing the total number of submatrices across all column pairs that sum up to the target value.\n\n\n\n# Complexity\n- Time complexity:O(m^2*n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(m*n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int n = matrix.size();\n        int m = matrix[0].size();\n\n        int count =0;\n\n        for(int i=0;i<m;i++){\n            vector<int> cumuColSum(n,0);\n\n            for(int j=i;j<m;j++){\n                unordered_map<int,int> freq;\n                int sum = 0;\n                for(int k=0;k<n;k++){\n                    cumuColSum[k] = matrix[k][j] + cumuColSum[k];\n                    freq[sum]++;\n                    sum += cumuColSum[k];\n                    count += freq[sum-target];\n                    \n                }\n            }\n        }\n\n        return count;\n    }\n};\n```
['C++']