405. 和为零的子矩阵(经典)

405. 和为零的子矩阵

中文English

给定一个整数矩阵，请找出一个子矩阵，使得其数字之和等于0.输出答案时，请返回左上数字和右下数字的坐标。

如果有多个答案, 你可以返回其中任意一个.

样例

样例 1:

输入:
[
  [1, 5, 7],
  [3, 7, -8],
  [4, -8 ,9]
]
输出: [[1, 1], [2, 2]]

样例 2:

输入: 
[
  [0, 1],
  [1, 0]
]
输出: [[0, 0], [0, 0]]

挑战

O(n3) 时间复杂度。

输入测试数据 (每行一个参数)如何理解测试数据？

 前缀和 （i到j中间求前缀和，x轴）

class Solution:
    """
    @param: matrix: an integer matrix
    @return: the coordinate of the left-up and right-down number
    """
    def submatrixSum(self, matrix):
        # write your code here
        #前缀和写法，记录竖向前缀和，然和横向相加
        
        len_x, len_y = len(matrix), len(matrix[0])
        
        #固定第一个x轴坐标
        for i in range(len_x):
            #第一个从第i行往下遍历寻找,存储的是i到j行中间得第z个前缀和
            array = [0 for _ in range(len_y)]
            
            #内层循环，第二个坐标(固定第二个x轴坐标)
            for j in range(i, len_x):
                #在i到j中间，求得第二个坐标的前缀和 - 第一个坐标的前缀和即为当前该矩阵的子数组和
                prefixsum_hash = {0: -1}
                #每次都需要更新前缀和，每个y轴坐标，需要取出所有相对应坐标的前缀和，所以需要在里面更新
                prefixsum = 0 
                for z in range(len_y):
                    #求当前第一个坐标i和第二个坐标j，的第z个竖向前缀和(i > j 横向坐标里面的第z个竖向和)
                    array[z] += matrix[j][z]
                    #加上竖向前缀和，依次加便是前i到j行，前z列(包含j列)的前缀和 
                    prefixsum += array[z]
                    
                    #如果之前已经记录过prefixsum的话，则返回第二个坐标
                    if (prefixsum in prefixsum_hash):
                        #前z个，但是要返回的是z + 1开始的纵坐标(第一个)
                        return [(i, prefixsum_hash[prefixsum] + 1), (j, z)]
                    
                    #记录下来，如果之前不存在该前缀和的话,只需要记录纵坐标即可,横坐标的时候在上面会循环判断取
                    prefixsum_hash[prefixsum] = z 
            
        #如果最终仍没有则返回None
        
        return None