C++ Prefix sums time complexity O(row*col*min(row, col))||399 ms Beats 95.82%
Intuition\n Describe your first thoughts on how to solve this problem. \nCompute prefix sums for rows or prefix sums for columns in either way.\nThen use hash m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCompute prefix sums for rows or prefix sums for columns in either way.\nThen use hash map.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIdea like in [Leetcode 560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/description/)\n\nif col>row, compute it in an alternative way which has TC $O(row^2\\times col)$\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(row\\times col\\times \\min(row, col))$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(row\\times col)$\n# Code ||399 ms Beats 95.82%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int alternative(vector<vector<int>>& matrix, int target, int n, int m){\n        // Calculate prefix sums for every column\n        for (int j = 0; j < m; j++) {\n            for (int i = 1; i < n; i++) {\n                matrix[i][j] += matrix[i-1][j];\n            }\n        }\n        int ans= 0; \n        for(int r0 = 0 ; r0 < n ; r0++){\n            for(int r = r0 ; r < n; r++){\n                unordered_map<int , int> f;\n                f[0] = 1;\n                int sum =0;\n                for(int c = 0 ; c < m ; c++){\n                    int prev=(r0==0) ? 0 : matrix[r0-1][c];\n                    sum += matrix[r][c]-prev;\n                    int x=sum-target;\n                    ans += f.count(x) ? f[x] : 0;\n                    f[sum]++;\n                }\n            }\n        }\n        return ans;\n    }\n\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int n = matrix.size(), m = matrix[0].size();\n        if ( m>n ) return alternative(matrix, target, n, m);\n\n        // Calculate prefix sums for every row\n        for (int i = 0; i < n; i++) {\n            for (int j = 1; j < m; j++) {\n                matrix[i][j] += matrix[i][j-1];\n            }\n        }\n        int ans= 0; \n        for(int c0 = 0 ; c0 < m ; c0++){\n            for(int c = c0 ; c < m; c++){\n                unordered_map<int , int> f;\n                f[0] = 1;\n                int sum =0;\n                for(int r = 0 ; r < n ; r++){\n                    int prev=(c0==0) ? 0 : matrix[r][c0-1];\n                    sum += matrix[r][c]-prev;\n                    int x= sum-target;\n                    ans += f.count(x) ? f[x] : 0;\n                    f[sum]++;\n                }\n            }\n        }\n        return ans;\n    }\n};\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Hash Table', 'Prefix Sum', 'C++']