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

脚本之家

 关注

“脚本之家

”，与百万开发者在一起

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

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

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

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