b2b电子商务网站商务模式互联网服务平台

leetcode周赛遇到的hard题，题目在最后，当时做的时候毫无头绪，因为本人差分做的也很少，所有完全没往差分上面想，然后就开始坐牢。所以总结一下前缀和以及差分数组的知识点。

一维前缀和

一次区间和

假设现在有个需求，给想知道指定一维数组某个区间的和，怎么求？

例如数组[1,2,3,4,5,4,3,2,3]，数组长度为n，我想知道下标2到5区间内数组元素的和，最直观的做法如下

public int demo(int[] nums, int l, int r) {int sum = 0;for (int i = l; i <= r; i++) {sum += nums[i];}return sum;
}
复制代码

很显然，没有比这更优的解法了，时间复杂度O(n)，空间复杂度O(1)

多次求区间和

1、假设我不仅需要求区间[2,5]的和，我还需要求[1,3]、[4,5]...的和，即我会给m个[l,r]，但是数组nums是固定的，同样的，依然可以用上述方法解决，你每次都调用demo方法就可以了，但是这样的时间复杂度是O(n*m)了，很容易超时。

2、对于这种情况我们可以用到前缀和的思想，构造一维数组的前缀和

原来的数组 nums [1,2,3,4,5,4,3,2,3]前缀和数组 sum  [1,3,6,10,15,19,22,24,27]
复制代码

构造代码如下

for (int i = 1; i < nums.length; i++) {nums[i] += nums[i - 1];
}
复制代码

3、现在有了前缀和数组，我们该怎么求区间[l,r]的范围和呢？

不难想到，求区间[l,r]的和，就是求(1+2+3+...+r)-(1+2+3+...+l-1)的和

怎么理解，比如我有个数组是[0,1,2,3,4,5,6,7,8,9,10]，我要求[2,4]的和，可以先求[0,4]的和，就是0+1+2+3+4，再求[0,1]的和，就是0+1，那么0+1+2+3+4是不是比0+1多了2+3+4，是不是正好就是区间[2,4]的和？

通解就是sum[l,r] = sum[r] - sum[l - 1] (这里l-1会越界，读者可以特判，或者让数组的长度为n+1)

二维前缀和

类似一维前缀和，如果多次求区间内范围和，就可以用到二维前缀和的思想，那么二维数组的区间是什么？ 假设红色矩阵左上角的坐标是[i,j],右下角的坐标是[m,n]，用这两个坐标是不是可以圈出这个矩阵了

一次区间和

那现在我这个红色矩阵的和是不是很好求了，直接遍历就可以了

public int demo(int[][] matrix, int i, int j, int m, int n) {int sum = 0;for (int k = i; k <= m; k++) {for (int l = j; l <= n; l++) {sum += matrix[k][l];}}return sum;
}
复制代码

多次求区间和

如果我想求多次呢？那每一次都像上面的解法就很慢了，有没有一行代码就能求出来的解法，当然有，我们可以先构造二维前缀和，之后利用二维前缀和数组，就可以一行代码求出区间的和了

1、我们先构造二维前缀和数组，利用如下代码即可

public int[][] demo(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;int[][] sum = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + matrix[i - 1][j - 1] - sum[i - 1][j - 1];}}return sum;
}
复制代码

怎么理解？如下图，比如我想求左上角到红色圈圈的矩阵的和，是不是等于两个绿色的矩阵的和加上红色圈圈的值，减去绿色矩阵重叠的部分？

我们求到的前缀和数组如下

这一排0主要是为了防止下标越界，如果做特判的话会很耗时，代码也不够优雅

2、前缀和数组构造好了，我怎么能够快速知道矩阵[i,j]-[m,n]的和？

比如我想知道红色矩阵的和，实际上就是绿色矩阵的和减去两个蓝色矩阵的和再加上蓝色重叠矩阵的和 代码如下

/*** sum为前缀和数组, 区间为[i,j]到[m,n]的矩阵，ijmn的下标是原数组的下标*/
public int getSum(int[][] sum, int i, int j, int m, int n) {i += 1;j += 1;m += 1;n += 1;return sum[m][n] - sum[m][j - 1] - sum[i - 1][n] + sum[i - 1][j - 1];
}
复制代码

一维差分

什么是差分数组，我个人觉得比前缀和更不好理解，首先我们找个场景了解一下什么情况下会用到差分数组，例如力扣的这道题 1109. 航班预订统计

一次区间整体加x

如果航班预订表bookings的长度为1，那么应该怎么写，比如[1,2,10]，n=5,我们可以构造一个空数组 [0,0,0,0,0]，然后for (int i = 1; i <= 2; i++) nums[i] += 10; 这样就得到了[0,10,10,0,0],但是bookings的长度会很大，有没有一种方法，可以快速在某个区间让所有的数加上x，这就是我们要说的差分

多次区间整体加x

首先要知道差分数组的定义：差分数组求前缀和可以得到原数组，diff[i] = nums[i] - nums[i - 1]

比如原数组[1,10,10,1,1]按照定义构造差分数组就是[1,9,0,-9,0]，厉害的在于根据差分数组可以反推原数组，差分数组求前缀和数组就是原数组，读者可以试着推一下，这个必须要理解。

那么现在我想在差分数组[0,10,0,-10,0]，区间[2,3]上都加上20应该怎么往差分数组上写，往2,3上加20，是不是往2上加10，然后到时候求前缀和的时候，坐标>=2的数，都会加上20，但是我们需要到坐标>3的地方就截止，那是不是可以再坐标为4的地方-20，这样求前缀和的时候，坐标>3的数就不会影响到了。

根据以上步骤，很容易就可以写出上面那题的答案

public int[] corpFlightBookings(int[][] bookings, int n) {int[] diff = new int[n];for (int[] booking : bookings) {diff[booking[0] - 1] += booking[2];if(booking[1] < n) diff[booking[1]] -= booking[2];}// 差分数组求前缀和->原数组for (int i = 1; i < n; i++) {diff[i] += diff[i - 1];}return diff;
}
复制代码

二维差分

1、二维差分数组怎么理解？比如我现在有一个矩阵，即二维差分数组

如果我让差分数组变成这样

那对这个差分数组求前缀和数组会得到

显然，如果我们对差分数组的某个一数字，增加1，求完前缀和数组发现，它会影响当前坐标，到右下角构成的矩阵，让整个矩阵都增加1，那么我们是不是可以猜测，想让二维矩阵的所有数整体加减X，用差分数组是不是只需要改动几个数字就可以了。

2、刚才我们只让右下角的矩阵整体增加1，如果我想让红色矩阵整体增加1，应该怎么修改差分数组呢？

如果我让差分数组变成这样

那么求完前缀和得到原数组就是这样

我们会发现离我们需要的原数组有点不一样，我们理想的原数组应该是让红色部分增加四个1，红色之外的应该是0才对，也就是说，超出红色矩阵的部分不应该加了，如果我们让差分数组构建成这样

那得到的前缀和数组如下

发现我们改了两个-1之后，求前缀和的时候会有重叠减少的部分，这部分就是红色圆圈一直到右下角的矩阵整体加了减少了1，刚才我们讲过，让一个到右下角的矩阵整体加1，就是让差分数组里面，红色圈圈的数加1，到时候求出的前缀和数组，从左上角一个到右下角，就会整体加1，所以我们构建差分数组的时候，还需要改动红色圈圈这个位置就可以了，最终的差分数组如下，用这个差分数组求前缀和数组，就能够得到红色矩阵里面都是1的结果了。

通解如下

想让矩阵[i,j]到[m,n]整体加x，对差分数组应该有如下操作

diff[i][j] += x (此时求前缀和数组的话从[i,j]一直到右下角都是加了x的）
diff[m + 1][j] -= x, diff[i][n + 1] -= x (此时结果接近正确，只有[m+1,n+1]到右下角都是-x的)
diff[m + 1][n + 1] += x ([m+1,n+1]到右下角都加x，得到正确结果）
复制代码

如果我们多次对某个区间加减x，最后只需要把差分数组求出前缀和数组，就能够得到最后的结果了。

实战题

可以自行去搜索一些前缀和以及差分的mid题目，如果熟练了可以做下面的题目

2132. 用邮票贴满网格图

首先，我们需要贴邮票，我们遍历二维数组grid，判断这个点是不是超出grid了（这里可以放在for循环里面判断），没有超出就继续判断有没有障碍物[x]，怎么判断我现在要贴的这个位置有没有障碍物[x]？

1、我们需要对grid构造一个前缀和数组，根据这个数组，可以快速知道某个矩阵内有没有障碍物，即判断这个区间的和是不是0，如果是0就没有障碍物。

2、如果没有障碍物，也就是可以贴邮票，那么我们应该利用差分数组，快速的将整个区间整体+1。

3、遍历完所有能贴邮票的区间后，用差分数组构建出前缀和数组，如果得到的前缀和数组中有为0的点，并且grid中这个点不是[x]，那么说明有没贴到的地方。

public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {int m = grid.length;int n = grid[0].length;// 为什么是m+1、n+1? 因为求前缀和的时候不需要特判int[][] sum = new int[m + 1][n + 1];// 为什么是m+2、n+2？因为求前缀和的时候需要前一位的数据// 而后一位的数据在这个操作中会出现（让矩阵[i,j]到[m,n]整体加x）为了避免数组越界和特判，所有用了m+2,n+2int[][] diff = new int[m + 2][n + 2];// 构建前缀和数组，方便快速判断矩阵内有没有[x]for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + grid[i - 1][j - 1] - sum[i - 1][j - 1];}}for (int i = 1; i + stampHeight - 1 <= m; i++) {for (int j = 1; j + stampWidth - 1 <= n; j++) {int p = i + stampHeight - 1;int q = j + stampWidth - 1;// 判断区间[i,j]到[p, q]内有没有[X]int x = sum[p][q] + sum[i - 1][j - 1] - sum[p][j - 1] - sum[i - 1][q];// 如果没有[x]，[i,j]到[p,q]构成的矩阵内整体+1if (x == 0) {diff[i][j] += 1;diff[p + 1][j] -= 1;diff[i][q + 1] -= 1;diff[p + 1][q + 1] += 1;}}}// 差分数组转换成前缀和数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {diff[i][j] = diff[i - 1][j] + diff[i][j - 1] + diff[i][j] - diff[i - 1][j - 1];}}// 贴完了所有邮票，判断有没有没贴到的格子for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (diff[i][j] == 0 && grid[i - 1][j - 1] == 0) return false;}}return true;
}

作者：朝如青丝
链接：https://juejin.cn/post/7051851325746708511