Leetcode: 1074. Number of Submatrices That Sum to Target

Mistake: Did not try hard to solve alternative problem. I saw the transformation but couldn't see the linear solution for it.
Is there an alternative problem easier to solve? Given an array of numbers and a target \(t\), find the number of subarrays which sum is equal to \(t\). Be \(p[i]=\sum_{0 \leq j \leq i}a[j]\). The number of valid subarrays ending on \(i\) is the number of times that \(p[i]-target\) appeared in \(p[0..(i-1)]\) plus 1 if \(p[i]=t\). We can transform the 2D problem in the 1D by keeping an accumulated sum for each column and creating the array of numbers after fixing two rows \(i0\) and \(i0\). Time complexity is \(O(n^2 \times m)\) and space complexity is \(O(n \times m)\).

from typing import List
from collections import defaultdict


class Solution:
    def numSubmatrixSumTarget(self, m: List[List[int]], target: int) -> int:
        N = len(m)
        M = len(m[0])

        csum = [[0] * M for _ in range(N)]
        for i in range(N):
            for j in range(M):
                csum[i][j] = m[i][j]
                if i > 0:
                    csum[i][j] += csum[i - 1][j]
        ans = 0
        for i0 in range(N):
            for i1 in range(i0, N):
                freq = defaultdict(int)
                cur = 0
                for j in range(M):
                    cur += csum[i1][j]
                    if i0 > 0:
                        cur -= csum[i0 - 1][j]
                    ans += freq[cur - target]
                    if cur == target:
                        ans += 1
                    freq[cur] += 1
        return ans


assert Solution().numSubmatrixSumTarget([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0) == 4
assert Solution().numSubmatrixSumTarget([[1, -1], [-1, 1]], 0) == 5
assert Solution().numSubmatrixSumTarget([[904]], 0) == 0