Python | prefix sum + hashmap, with explanation
To solve this probelm, let us solve 560. Subarray Sum Equals K at first.\n\n### 560. Subarray Sum Equals K\nThe basic idea it to handle this problem with hashma
To solve this probelm, let us solve [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) at first.\n\n### 560. Subarray Sum Equals K\nThe basic idea it to handle this problem with `hashmap`. The hashmap will store with the key being any particular `sum`, and the value being the number of time it has happened yet. Suppose we iterate the arrary from left to right and keep track of cumulative sum up to `i` in each position.\n\nIf there is an increase of `k` in `preSum[i]`, we can find `preSum[j] = preSum[i] + k`. (j > i)\n\nThe origin problem `find a subarry whose sum equals to k (preSum[j] - preSum[i])` can be changed to `find a subarray whose sum equals to preSum[i] (preSum[j] - k)`\n\nSo, the solution is here:\n```python\n```python\nclass Solution:\n    def subarraySum(self, nums: List[int], k: int) -> int:\n        ans = 0\n        pre_sum = 0\n        res = defaultdict(int)\n        res[0] = 1 # it means that we\'ve already seen sum of 0 once before iterating the list.\n        \n        for num in nums:\n            pre_sum += num\n            ans += res[pre_sum - k]\n            res[pre_sum] += 1\n        return ans\n```\n\n### 1074. Number of Submatrices That Sum to Target\nActually, this problem is a variation of `560`. We enumerate the submatrixs by setting different `upper` and `lower` boundaries. Then we calculate the `sum` of each column. So the origin problem can be changed to:\n- Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.\n\nFor the calculation of sum of each column, every time we extend lower boundary `j` downwards, the elements in the `jth` row of the matrix are added to the `sum`.\n\n```python\nclass Solution:\n    def numSubmatrixSumTarget(self, M: List[List[int]], T: int) -> int:\n        def subarrSum(nums, target):\n            res = defaultdict(int)\n            res[0] = 1\n            ans, pre_sum = 0, 0\n            \n            for num in nums:\n                pre_sum += num\n                ans += res[pre_sum - target]\n                res[pre_sum] += 1\n            return ans\n                \n                \n        rows, cols = len(M), len(M[0])\n        ans = 0\n        for i1 in range(rows):\n            total = [0]*cols\n            for i2 in range(i1, rows):\n                for j in range(cols):\n                    total[j] += M[i2][j]\n                ans += subarrSum(total, T)\n        return ans\n```
['Prefix Sum', 'Python']