以下文章来源于负雪明烛 ,作者负雪明烛
1000 篇算法题解的作者,国内互联网大厂程序员,技术分享爱好者。 爱好算法题解写作,擅长深入浅出讲解计算机知识,乐于分享大厂见闻。和读者一起刷算法题,拿 Offer,交朋友!
出品 | 负雪明烛 (ID:fuxuemingzhu_writing)
今天讲的知识是「前缀和」,这是面试常考、又非常容易掌握的算法题技巧。你只用花 15 分钟看完本文就能学会,然后就能秒杀面试遇到的「前缀和」题目。
前缀和,英文是 preSum,名字很可怕,但它却是个窗户纸,一捅就破。
为了了解背景,咱们先看 LeetCode 上一个简单题目:1480. 一维数组的动态和。这个题让我们求
runningSum[i] = sum(nums[0]…nums[i]),如果你没有了解过「前缀和」,可能会写出两重循环:每个 runningSum[i],累加从 位置到 位置的 nums[i]。即,写出下面的代码:
vector<int> runningSum(vector<int>& nums) {
const int N = nums.size();
vector<int> preSum(N, 0);
for (int i = 0; i < N; ++i) {
int sum = 0;
for (int j = 0; j <= i; ++j) {
sum += nums[j];
}
preSum[i] = sum;
}
return preSum;
}
两重循环的时间复杂度是 ,效率比较低。
其实我们只要稍微转变一下思路,就发现没必要用两重循环。
runningSum[i] = sum(nums[0]…nums[i]),runningSum[i + 1] = sum(nums[0]…nums[i]) + nums[i + 1]= runningSum[i] + nums[i + 1]。就是这个简单的转换,让我们可以省去内层的循环。写出的代码如下:
vector<int> runningSum(vector<int>& nums) {
const int N = nums.size();
vector<int> preSum(N, 0);
for (int i = 0; i < N; ++i) {
if (i == 0) {
preSum[i] = nums[i];
} else {
preSum[i] = preSum[i - 1] + nums[i];
}
}
return preSum;
}
如果理解了上面的内容,那么我告诉你,preSum 数组其实就是「前缀和」!就是这么简单!
「前缀和」 是从 nums 数组中的第 0 位置开始累加,到第 位置的累加结果,我们常把这个结果保存到数组 preSum 中,记为 preSum[i]。
在前面计算「前缀和」的代码中,计算公式为 preSum[i] = preSum[i - 1] + nums[i] ,为了防止当 i = 0 的时候数组越界,所以加了个 if (i == 0) 的判断,即 i == 0 时让 preSum[i] = nums[i]。
在其他常见的写法中,为了省去这个 if 判断,我们常常把「前缀和」数组 preSum 的长度定义为原数组的长度 + 1。preSum 的第 0 个位置,相当于一个占位符,置为 0。
那么就可以把 preSum 的公式统一为 preSum[i] = preSum[i - 1] + nums[i - 1],此时的 preSum[i] 表示 nums 中 元素左边所有元素之和(不包含当前元素 。
下面以 [1, 12, -5, -6, 50, 3] 为例,用动图讲解一下如何求 preSum。
上图表示:
preSum[0] = 0;preSum[1] = preSum[0] + nums[0];preSum[2] = preSum[1] + nums[1];...求数组前 个数之和,是「前缀和」数组的定义,所以是最基本的用法。举例而言:
nums 数组中的前 2 个数的和(即 ),直接返回 即可。nums 数组中所有元素的和(即 ),直接返回 即可。利用 preSum 数组,可以在 的时间内快速求出 nums 任意区间 (两端都包含) 内的所有元素之和。
公式为:
什么原理呢?其实就是消除公共部分即 0~i-1 部分的和,那么就能得到 i~j 部分的区间和。
注意上面的式子中,使用的是 preSum[j + 1] 和 preSum[i],需要理解为什么这么做。(如果理解不了的知识,那就记不住,所以一定要理解)
preSum[j + 1] 表示的是 nums 数组中 [0,j] 的所有数字之和(包含 和 )。preSum[i]表示的是 nums数组中 [0, i - 1] 的所有数字之和(包含 和 )。nums数组中 [i, j] 的所有数字之和。在了解「前缀和」是什么、有什么用之后,咱们练习一个简单的例题。这个题是 303. 区域和检索 - 数组不可变。
题意是给出了一个整数数组 nums,当调用 sumRange(i, j)函数的时候,求数组 nums 中 到 的所有元素总和(包含 和 )。
看到这里,相信大家已经都知道了,直接使用「前缀和」不就秒杀了嘛!
下面,我贴一下三种语言的代码。
class NumArray:
def __init__(self, nums: List[int]):
N = len(nums)
self.preSum = [0] * (N + 1)
for i in range(N):
self.preSum[i + 1] = self.preSum[i] + nums[i]
def sumRange(self, i: int, j: int) -> int:
return self.preSum[j + 1] - self.preSum[i]
class NumArray {
public:
NumArray(vector<int>& nums) {
const int N = nums.size();
preSum.resize(N + 1);
for (int i = 0; i < N; ++i) {
preSum[i + 1] = preSum[i] + nums[i];
}
}
int sumRange(int i, int j) {
return preSum[j + 1] - preSum[i];
}
private:
vector<int> preSum;
};
class NumArray {
private int[] preSum;
public NumArray(int[] nums) {
final int N = nums.length;
preSum = new int[N + 1];
for (int i = 0; i < N; ++i) {
preSum[i + 1] = preSum[i] + nums[i];
}
}
public int sumRange(int i, int j) {
return preSum[j + 1] - preSum[i];
}
}
preSum[j + 1] 和 preSum[i],时间复杂度是 。算法题目就像一棵大树长出的很多树叶,虽然每片叶子长得都不同,但是它们都有共同的一个主干。算法题的知识点是有限的,有大量的题目都是同一个解法批了不同的皮。
我们以 643. 子数组最大平均数 I 为例,这个题目要求数组 nums 中所有长度为 k 的连续子数组中的最大的平均数。这个题可以用「前缀和」来解决,也可以用固定大小为 k 的「滑动窗口」来解决。
要求大小为 k 的窗口内的最大平均数,可以求 区间的最大「和」再除以 k,即要求 (preSum[i + k] - preSum[i]) / k 的最大值。
总之,如果题目要求「区间和」的时候,那么就可以考虑使用「前缀和」。
另外一种拓展,是求二维矩阵的「前缀和」。比如第 304. 二维区域和检索 - 矩阵不可变。当「前缀和」拓展到二维区间时,可以用下面的思路求解。
我们定义 preSum[i][j] 表示 从 [0,0] 位置到 [i,j] 位置的子矩形所有元素之和。
如果求 preSum[i][j] 的递推公式为:
可以用下图帮助理解:
减去 的原因是 和 中都有 ,即加了两次 ,所以需要减去一次 。
前面已经求出了数组中从 [0,0] 位置到 [i,j] 位置的 preSum。
如果要求 [row1, col1] 到 [row2, col2] 的子矩形的面积的话,用 preSum 计算时对应了以下的递推公式:
同样利用一张图来说明:
加上子矩形 面积的原因是 和 中都有 ,即减了两次 ,所以需要加上一次 。
弄明白这个原理之后,题目就不难解决了。
nums的指定区间 内所有元素的「和」。<END>
程序员专属T恤
推荐阅读:
腾讯面试题:64匹马,8赛道,找出最快的4匹最少要几次?
一文搞懂二分查找算法!