Python Solution O(n^3) beats 98%
This question is related to https://leetcode.com/problems/subarray-sum-equals-k/. We can use the same idea to find out the number of subarray with target sum fo
This question is related to https://leetcode.com/problems/subarray-sum-equals-k/. We can use the same idea to find out the number of subarray with target sum for one row in linear time. Basically, we generate O(m^2) combinations of rows and apply O(n) algorithm to find the target sum for each combination. \n\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        if not matrix:\n            return 0\n        \n        def num_for_one_row(nums):\n            prev = {}\n            prev[0] = 1\n            cur_sum = 0\n            ans = 0\n            for num in nums:\n                cur_sum += num\n                if cur_sum - target in prev:\n                    ans += prev[cur_sum - target]\n                if cur_sum not in prev:\n                    prev[cur_sum] = 1\n                else:\n                    prev[cur_sum] += 1\n            return ans \n        \n        res = 0\n        m = len(matrix)\n        n = len(matrix[0])\n        \n        for i in range(m):\n            nums = [0]*n\n            for j in range(i,m):\n                for k in range(n):\n                    nums[k]+=matrix[j][k]\n                res += num_for_one_row(nums)\n                \n        return res\n```\n\nIn this solution, the time complexity is O(m^2*n)  where m is the number of rows and n is the number of columns. The space complexity is O(n).
['Python', 'Python3']