Python/Go O(w^2 * h) by prefix sum [w/ Hint]
Python O(w^2 * h)  by prefix sum\n\n---\n\nHint:\n\nThis is 2D extented version of Leetcode 560 Subarray Sum Equals K\n\nThe concept of prefix sum and dictionar
Python O(w^2 * h)  by prefix sum\n\n---\n\n**Hint**:\n\nThis is **2D extented version** of [Leetcode 560 Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)\n\nThe concept of **prefix sum** and **dictionary** technique can be used again to help us.\n\n---\n\n**Implementation** by dictionary in Python\n\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        \n        # height and width of matrix\n        h, w = len(matrix), len(matrix[0])\n        \n\t\t\n        # update prefix sum on each row\n        for y in range(h):\n            for x in range(1,w):\n                matrix[y][x] = matrix[y][x] + matrix[y][x-1]\n                \n        \n        # number of submatrices that sum to target\n        counter = 0\n        \n        # sliding windows on x-axis, in range [left, right]\n        for left in range(w):\n            for right in range(left, w):\n                \n                # accumulation of area so far\n                accumulation = {0: 1}\n                \n                # area of current submatrices, bounded by [left, right] with height y\n                area = 0\n                \n                # scan each possible height on y-axis\n                for y in range(h):\n                    \n                    if left > 0:\n                        area += matrix[y][right] - matrix[y][left-1]\n                    \n                    else:\n                        area += matrix[y][right]\n                    \n                    # if ( area - target ) exist, then target must exist in submatrices\n                    counter += accumulation.get( area - target, 0)\n                    \n                    # update dictionary with current accumulation area\n                    accumulation[area] = accumulation.get(area, 0) + 1\n        \n        return counter\n```\n\n---\n\n**Implementatin** by map in Go\n\n```\nfunc numSubmatrixSumTarget(matrix [][]int, target int) int {\n    \n    // height and width of matrix\n    h, w := len(matrix), len(matrix[0])\n    \n    // update prefix sum on each row\n    for y := 0 ; y < h ; y++{\n        for x:= 1 ; x < w; x++{\n            matrix[y][x] = matrix[y][x] + matrix[y][x-1]\n        }\n    }\n    \n    // number of submatrices that sum to target\n    counter := 0\n    \n    // sliding windows on x-axis, in range[left, right]\n    for left := 0 ; left < w ; left ++{\n        for right := left ; right < w ; right++{\n            \n            // accumulation for area so far\n            accumulation := map[int]int{ 0 : 1}\n            \n            // area of current submatrices, bounded by [left, right] with height y\n            area := 0\n            \n            // scan each possible height on y-axis\n            for y := 0 ; y < h ; y++{\n                \n                if left > 0 {\n                    area += matrix[y][right] - matrix[y][left-1]\n                }else{\n                    area += matrix[y][right]\n                }\n                \n                // if ( area - target ) exists, then target must exist in submatrices\n                counter += accumulation[ (area - target) ]\n                \n                // update dictionary with current accumulation area\n                accumulation[area] += 1\n                \n            }\n            \n        }//end of right loop\n        \n    }//end of left loop\n    \n    return counter\n    \n}\n```\n\n---\n\nRelated leetcode challenge:\n\n[1]  [Leetcode 560 Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)\n\n---\n\nReference:\n\n[1] [Python official docs about dictioanry](https://docs.python.org/3/tutorial/datastructures.html#dictionaries)\n\n[2] [Golang official docs about map[]](https://blog.golang.org/maps)\n\n[3] [Wiki: prefix sum](https://en.wikipedia.org/wiki/Prefix_sum)
['Sliding Window', 'Prefix Sum', 'Python', 'Go', 'Python3']