Lintcode405 Submatrix Sum solution 题解
发布在刷题能手——Lintcode 题解2018年4月14日view:363
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

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

【题目链接】

www.lintcode.com/en/problem/submatrix-sum/

【题目解析】

这道题和求数组中哪些元素和为0的解决方法一样,只是数组中求的是前i个元素和前j个元素和相等,则i-j元素和为0,而这里只是变成2维的而已。

sum[i][j]表示matrix[0][0]到matrix[i-1][j-1]所有元素的和。

建立sum矩阵,为n+1行,m+1列。将第0行和第0列都初始化为0。

遍历matrix,根据公式 sum[i][j] = matrix[i - 1][j - 1] + sum[i][j - 1] + sum[i - 1][j] -sum[i - 1][j - 1] 计算所有sum。

然后取两个row:l1, l2。用一个线k从左到右扫过l1和l2,每次都用diff=sum[l1][k]-sum[l2][k]来表示l1-l2和0-k这个矩形元素的sum。如果在同一个l1和l2中,有两条线(k1,k2)的diff相等,则表示l1-l2和k1-k2这个矩形中的元素和为0。

【参考答案】

www.jiuzhang.com/solutions/submatrix-sum/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏