[Java/C++/Python] Find the Subarray with Target Sum
Intuition\nPreaquis: 560. Subarray Sum Equals K\nFind the Subarray with Target Sum in linear time.\n\n\n# Explanation\nFor each row, calculate the prefix sum.\n
# Intuition\nPreaquis: [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/description/)\nFind the Subarray with Target Sum in linear time.\n<br>\n\n# Explanation\nFor each row, calculate the prefix sum.\nFor each pair of columns,\ncalculate the accumulated sum of rows.\nNow this problem is same to, "Find the Subarray with Target Sum".\n<br>\n\n# Complexity\nTime `O(mnn)`\nSpace `O(m)`\n<br>\n\n**Java**\n```java\n    public int numSubmatrixSumTarget(int[][] A, int target) {\n        int res = 0, m = A.length, n = A[0].length;\n        for (int i = 0; i < m; i++)\n            for (int j = 1; j < n; j++)\n                A[i][j] += A[i][j - 1];\n        Map<Integer, Integer> counter = new HashMap<>();\n        for (int i = 0; i < n; i++) {\n            for (int j = i; j < n; j++) {\n                counter.clear();\n                counter.put(0, 1);\n                int cur = 0;\n                for (int k = 0; k < m; k++) {\n                    cur += A[k][j] - (i > 0 ? A[k][i - 1] : 0);\n                    res += counter.getOrDefault(cur - target, 0);\n                    counter.put(cur, counter.getOrDefault(cur, 0) + 1);\n                }\n            }\n        }\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    int numSubmatrixSumTarget(vector<vector<int>>& A, int target) {\n        int res = 0, m = A.size(), n = A[0].size();\n        for (int i = 0; i < m; i++)\n            for (int j = 1; j < n; j++)\n                A[i][j] += A[i][j - 1];\n\n        unordered_map<int, int> counter;\n        for (int i = 0; i < n; i++) {\n            for (int j = i; j < n; j++) {\n                counter = {{0,1}};\n                int cur = 0;\n                for (int k = 0; k < m; k++) {\n                    cur += A[k][j] - (i > 0 ? A[k][i - 1] : 0);\n                    res += counter.find(cur - target) != counter.end() ? counter[cur - target] : 0;\n                    counter[cur]++;\n                }\n            }\n        }\n        return res;\n    }\n```\n\n**Python:**\n```py\n    def numSubmatrixSumTarget(self, A, target):\n        m, n = len(A), len(A[0])\n        for row in A:\n            for i in xrange(n - 1):\n                row[i + 1] += row[i]\n        res = 0\n        for i in xrange(n):\n            for j in xrange(i, n):\n                c = collections.defaultdict(int)\n                cur, c[0] = 0, 1\n                for k in xrange(m):\n                    cur += A[k][j] - (A[k][i - 1] if i > 0 else 0)\n                    res += c[cur - target]\n                    c[cur] += 1\n        return res\n```\n
[]