面试必会的算法题——前缀和

 关注“脚本之家”，与百万开发者在一起

出品 | 负雪明烛 （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 中 到 的所有元素总和（包含 和 ）。

看到这里，相信大家已经都知道了，直接使用「前缀和」不就秒杀了嘛！

下面，我贴一下三种语言的代码。

1. Python

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]

1. C++

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;
};

1. Java

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];
    }
}

复杂度分析

• 空间复杂度：定义「前缀和」数组，需要 的空间，所以空间复杂度是 ；
• 时间复杂度：
• 初始化「前缀和」数组，需要把数组遍历一次，时间复杂度是 ；
• 求 [i, j] 范围内的区间和，只用访问 preSum[j + 1] 和 preSum[i]，时间复杂度是 。

拓展

拓展一：隐藏的「前缀和」

算法题目就像一棵大树长出的很多树叶，虽然每片叶子长得都不同，但是它们都有共同的一个主干。算法题的知识点是有限的，有大量的题目都是同一个解法批了不同的皮。

我们以 643. 子数组最大平均数 I 为例，这个题目要求数组 nums 中所有长度为 k 的连续子数组中的最大的平均数。这个题可以用「前缀和」来解决，也可以用固定大小为 k 的「滑动窗口」来解决。

要求大小为 k 的窗口内的最大平均数，可以求 区间的最大「和」再除以 k，即要求 (preSum[i + k] - preSum[i]) / k 的最大值。

总之，如果题目要求「区间和」的时候，那么就可以考虑使用「前缀和」。

拓展二：二维矩阵的「前缀和」

另外一种拓展，是求二维矩阵的「前缀和」。比如第 304. 二维区域和检索 - 矩阵不可变。当「前缀和」拓展到二维区间时，可以用下面的思路求解。

步骤一：求 preSum

我们定义 preSum[i][j] 表示 从 [0,0] 位置到 [i,j] 位置的子矩形所有元素之和。

如果求 preSum[i][j] 的递推公式为：

可以用下图帮助理解：

减去 的原因是 和 中都有 ，即加了两次 ，所以需要减去一次 。

步骤二：根据 preSum 求子矩形面积

前面已经求出了数组中从 [0,0] 位置到 [i,j] 位置的 preSum。

如果要求 [row1, col1] 到 [row2, col2] 的子矩形的面积的话，用 preSum 计算时对应了以下的递推公式：

同样利用一张图来说明：

加上子矩形 面积的原因是 和 中都有 ，即减了两次 ，所以需要加上一次 。

弄明白这个原理之后，题目就不难解决了。

总结

1. 「前缀和」原理非常简单，但却很实用，当遇到「区间和」问题的时候肯定躲不过它。
2. 「前缀和」计算方式是对数组进行了预处理，得到了从第 位置到第 位置的「和」。
3. 「前缀和」可以快速求出数组 nums的指定区间 内所有元素的「和」。
4. 「前缀和」的复杂度：
1. 空间复杂度是 ；
2. 初始化的时间复杂度是 ；
3. 求「区间和」的时间复杂度是。

<END>

程序员专属T恤

商品直购链接 👇

  推荐阅读：