面试中的基本算法问题 - 前缀和后缀

最编程 2024-06-15 10:30:06

...

大家好，我是负雪明烛。

「金九银十」秋招季开始了，相信很多同学已经在投简历、面试了。算法题是面试的必考点，如何在最短时间内，掌握最多最实用的算法知识呢？我正在本公众号写系列文章：《秋招必会的算法题》，这个系列努力用最通俗易懂的语言，讲解秋招最常见的、必会的算法知识，让大家的时间能获得最大的投资回报率。

后续文章请关注本公众号「负雪明烛」。

今天讲的知识是「前缀和」，这是面试常考、又非常容易掌握的算法题技巧。你只用花 15 分钟看完本文就能学会，然后就能秒杀秋招面试遇到的「前缀和」题目。

从「一维数组的动态和」说起

前缀和，英文是 preSum，名字很可怕，但它却是个窗户纸，一捅就破。

为了了解背景，咱们先看 LeetCode 上一个简单题目：1480. 一维数组的动态和。这个题让我们求 runningSum[i] = sum(nums[0]…nums[i])，如果你没有了解过「前缀和」，可能会写出两重循环：每个 runningSum[i]，累加从 $0$ 位置到 $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;
}

两重循环的时间复杂度是 $O(N^2)$ ，效率比较低。

其实我们只要稍微转变一下思路，就发现没必要用两重循环。

当已经求出 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 位置开始累加，到第 $i$ 位置的累加结果，我们常把这个结果保存到数组 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 中 $i$ 元素左边所有元素之和（不包含当前元素 $i$ ）。

下面以 [1, 12, -5, -6, 50, 3] 为例，用动图讲解一下如何求 preSum。 1614561004-TEQwGZ-303，preSum.gif 上图表示：

preSum[0] = 0;
preSum[1] = preSum[0] + nums[0];
preSum[2] = preSum[1] + nums[1];
...

「前缀和」有什么用

用途一：求数组前 $i$ 个数之和

求数组前 $i$ 个数之和，是「前缀和」数组的定义，所以是最基本的用法。举例而言：

如果要求 nums 数组中的前 2 个数的和（即 $sum(nums[0], nums[1])$ )，直接返回 $preSum[2]$ 即可。
同理，如果要求 nums 数组中所有元素的和（即 $sum(nums[0]..nums[length - 1])$ ），直接返回 $preSum[length]$ 即可。

用途二：求数组的区间和

利用 preSum 数组，可以在 $O(1)$ 的时间内快速求出 nums 任意区间 $[i, j]$ (两端都包含) 内的所有元素之和。

公式为： $sum(i, j) = preSum[j + 1] - preSum[i]$

什么原理呢？其实就是消除公共部分即 0~i-1 部分的和，那么就能得到 i~j 部分的区间和。

注意上面的式子中，使用的是 preSum[j + 1] 和 preSum[i]，需要理解为什么这么做。（如果理解不了的知识，那就记不住，所以一定要理解）

preSum[j + 1] 表示的是 nums 数组中 $[0, j]$ 的所有数字之和（包含 $0$ 和 $j$ ）。
preSum[i]表示的是 nums数组中 $[0, i - 1]$ 的所有数字之和（包含 $0$ 和 $i - 1$ ）。
当两者相减时，结果留下了 nums数组中 $[i, j]$ 的所有数字之和。

「前缀和」例题

在了解「前缀和」是什么、有什么用之后，咱们练习一个简单的例题。这个题是 303. 区域和检索 - 数组不可变。题意是给出了一个整数数组 nums，当调用 sumRange(i, j)函数的时候，求数组 nums 中 $i$ 到 $j$ 的所有元素总和（包含 $i$ 和 $j$ ）。

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

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

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]

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

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

复杂度分析

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

拓展

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

算法题目就像一棵大树长出的很多树叶，虽然每片叶子长得都不同，但是它们都有共同的一个主干。算法题的知识点是有限的，有大量的题目都是同一个解法批了不同的皮。我们以 643. 子数组最大平均数 I 为例，这个题目要求数组 nums 中所有长度为 k 的连续子数组中的最大的平均数。这个题可以用「前缀和」来解决，也可以用固定大小为 k 的「滑动窗口」来解决。

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

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

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

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

步骤一：求 preSum

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

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

$preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i][j]$

可以用下图帮助理解：

$S(O, D) = S(O, C) + S(O, B) - S(O, A) + D$

减去 $S(O, A)$ 的原因是 $S(O, C)$ 和 $S(O, B)$ 中都有 $S(O, A)$ ，即加了两次 $S(O, A)$ ，所以需要减去一次 $S(O, A)$ 。

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

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

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

$preSum[row2][col2] - preSum[row2][col1 - 1] - preSum[row1 - 1][col2] + preSum[row1 - 1][col1 - 1]$

同样利用一张图来说明：

$S(A, D) = S(O, D) - S(O, E) - S(O, F) + S(O, G)$

加上子矩形 $S(O, G)$ 面积的原因是 $S(O, E)$

上一篇：页面的总体布局分为以下几类--金块

下一篇：华为游戏中心发布二次元新游戏助推计划，持续挖掘全生命周期量收增长点

面试中的基本算法问题 - 前缀和后缀

用途一：求数组前 $i$ 个数之和

用途二：求数组的区间和

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

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

步骤一：求 preSum

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

Java HashMap 的数据结构和基本原理及其在 Jdk8、Jdk11 和 Jdk17 中的一些变化，以及一些常见问题。

C++ Basic 面试问题 | C++ 中的野生指针和悬空指针有何区别？

聊聊Netty面试中必知的基本概念问题

面试问题：React 的基本概念，以及遇到的 CPU 和 IO 问题

几个与 "堆栈和队列 "相关的面试算法问题