小而美的算法技巧：前缀和数组 :: labuladong的算法小抄

[labuladong]

文章链接点这里：小而美的算法技巧：前缀和数组

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

打卡打卡

[Leloz00]

难者居然就是我自己😢

[daleyzou]

强

[ebadboy]

preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和-----为什么要这样自定义？preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i, j] 的元素和--这样定义不好吗

[Yoka416]

赞同，我觉得这样更好理解！

[YUTING0907]

同意+1

[YUTING0907]

不过这样的话，第0行或者第0列的遍历需要🏠另外的逻辑

[labuladong]

怎么定义都可以可以，只要改一下 preSum 初始化的逻辑，把 0 行 0 列的数据初始化就行了

[xcfxr]

preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和-----为什么要这样自定义？preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i, j] 的元素和--这样定义不好吗

你这样维护的话 查询的时候 如果row1和col1为0就要单独讨论一下了。

[zhangmuwuge]

讨论哪几种情况呢，感觉不用讨论啊

[kaige212]

// 如果前⾯有这个前缀和，则直接更新答案
if (preSum.containsKey(sum0_j))
res += preSum.get(sum0_j);

这里去哈希表里面查找的时候，时间复杂度不是O(n)嘛？这里有点疑问，

[ZZULHF]

// base case
preSum.put(0, 1);
请问最后一题为什么加上这个？怎么理解？

[david820505]

@ZZULHF
看第一個例子 [1,1,1] ->[1,2,3]
沒有加入 0, 最後只能得到 "3-1 = 2", 而 2 則沒有對應到

主要是為了解決 accumulate sum == k 的情形

[labuladong]

// base case preSum.put(0, 1); 请问最后一题为什么加上这个？怎么理解？

结合定义理解：前缀和为 0 的子数组有 1 个。这就好像一个 base case，如果你的 map 里面没有一个初始的键，那你的整个算法最终得到的结果只能是 0。

[labuladong]

@kaige212 哈希表存取键值对性能是 O(1)

[jianhaojiang]

我裂开

[2176700277]

打卡

[acse-yw3821]

打卡

[Yzxsysu]

304中的if (m == 0 || n == 0) return; 是相当于先判断输入的矩阵是否合法吗？

[x43125]

打卡，

[LilJessHumble]

一开始还有点难以理解+1 -1的情况，其实在最后返回前，把给的所有参数都+1，把他变成是preSum[ i ] [ j ] 就表示[ 0，0，i，j ]的情况更好理解。

[yezire]

1.转换计算方式->前缀做差求值
2.padding 0

[yezire]

打卡d4

[baowenqian2001]

明白啦！感谢～

[yaofengyi899]

请教一下，按照题目要求，矩阵左上角为坐标原点 (0, 0)，那么 sumRegion([2,1,4,3]) 就是图中红色的子矩阵。这个函数是怎么看出是红色矩阵的？

[baowenqian2001]

已知起始索引从0开始（2,1,4,3）就是以坐标为（2,1）和（4,3）为左上角和右下角的矩阵

[yaofengyi899]

好的，谢谢佬

[Catboss1999]

在求一维前缀和中
for (int i = 1; i < preSum.size(); i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
这里应该是i<=preSum.size()吧？不然的话 当i=preSum.size()时，就跳出循环了，就不会把num[preSum.size() - 1]，即num的最后一个数加到前缀和中了

[zhangmuwuge]

preSum的长度已经+1 了，所以不会出现你说的这个问题

[tomFoxxxx]

打卡

[Quanticco]

前缀和这个技巧精彩！用空间换时间

[PvP-zzz]

打开

[EyeDroplyq]

打卡，附上详细注释的Java代码

    class NumMatrix {
        //二维数组来表示前缀和
        private int[][] presum;
        public NumMatrix(int[][] matrix) {
            int m=matrix.length;
            int n=matrix[0].length;
            presum=new int[m+1][n+1];
            //计算原点(0,0)到所有位置(i,j)的元素和
            for (int i = 1; i <=m ; i++) {
                for (int j = 1; j <=n ; j++) {
                    //（i,j）位置的前置和等于上一行的前缀和+前一列的前缀和+当前位置的元素-左上角位置的前缀和，因为加重复了
                    //其实也可以简单的理解为和下面方法中求[row1,col1,row2,col2]的前缀和一样，通过相邻的几个矩阵相加减来求
                    presum[i][j]=presum[i-1][j]+presum[i][j-1]+matrix[i-1][j-1]-presum[i-1][j-1];
                }
            }
        }

        //二维数组中的任何一个位置的前缀和可以有四个相邻的数组加减组成
        public int sumRegion(int row1, int col1, int row2, int col2) {
            //因为我们的presum前缀和数组整体右移和下移了一位，所以presum[i][j]其实求的前置和不包括(i,j)的
                return presum[row2+1][col2+1]-presum[row1][col2+1]-presum[row2+1][col1]+presum[row1][col1];
        }
    }

[jiuyuna]

mark：前缀和添0辅助，前缀积添1辅助。

[shiboys]

只能说，前缀和的算法真的很巧妙！

[Rayden-Xu]

def init(self, matrix: List[List[int]]):
m, n = (len(matrix), len(matrix[0]))
if m == 0 or n == 0:
return
self.preSum = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(m):
for j in range(n):
self.preSum[i+1][j+1] = self.preSum[i][j+1] + self.preSum[i+1][j] + matrix[i][j] - self.preSum[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
# 目标矩阵之和由四个相邻矩阵运算获得
return self.preSum[row2+1][col2+1] - self.preSum[row1][col2+1] - self.preSum[row2+1][ col1] + self.preSum[row1][ col1]
简单一点

[yichenCY]

确实 nice

[lawyuhang]

微微打卡一刷

[myg321]

打卡，加油