和为目标值的子矩阵个数

  1. 给一个矩阵,求子矩阵的个数,子矩阵满足和=target
  2. 解题思路:
    1. 假设矩阵有M行,N列
    2. 先确定矩阵的上边界m,0<=m<=M
    3. 再确定矩阵的下边界n,m<=n<=M
    4. 最后求每列的和,这样就得到一个list,该list中存储了每列的和(具体由上下边界确定,比如可以得到前一行的每列和,前两行的每列和,前三行的每列和等等,或者第二行的每列和,第二行到第三行的每列和,第二行到第四行的每列和等等)
    5. 每列的和是一个list,该问题就转成了,求一个list的子list个数,子list满足和=target,该问题的解题思路如下
      1. 利用前缀和求解:pre[i]=pre[i-1]+list[i]
      2. pre[j…i]=pre[i]-pre[j-1]
      3. 我们要求pre[j…i]=target的个数,等同于求pre[i]-pre[j-1]=target的个数,等同于求pre[i]-target的个数
      4. 所以我们只需要建立一个hash表mp,该表的key是pre[i]的值,value是出现的次数,mp[pre[i]]=count,然后我们只需要查找到mp[pre[i]-target]的个数进行累加即可
      5. 考虑到pre[i]-target=0的情况,因此初始化mp[0]=1
      6. class Solution:
            def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
                #求list的子list个数,子list的和=k,利用前缀和求解
                def sum(nums,k):
                    count=0
                    pre=0
                    mp=Counter([0])
                    for i in range(len(nums)):
                        pre+=nums[i]
                        if pre-k in mp:
                            count+=mp[pre-k]
                        mp[pre]+=1
                    return count
                re=0
                for m in range(len(matrix)):
                    total=[0]*len(matrix[0])
                    for n in range(m,len(matrix)):
                        for c in range(len(matrix[0])):
                            total[c]+=matrix[n][c]
                        re+=sum(total,target)
                return re
        作者:LeetCode-Solution
        链接:https://leetcode-cn.com/problems/power-of-four/solution/4de-mi-by-leetcode-solution-b3ya/
        来源:力扣(LeetCode)
        
        

发表评论

电子邮件地址不会被公开。 必填项已用*标注