LeetCode 例题精讲 | 18 前缀和：空间换时间的技巧

本文将教会你「前缀和」的算法套路，做出以下 LeetCode 例题：

• LeetCode 724. Find Pivot Index（Easy）

• LeetCode 560. Subarray Sum Equals K 和为K的子数组（Medium）

在设计算法时，时间复杂度始终是我们关注的重点。我们需要让算法的时间复杂度尽可能低，追求运行效率。有些时候，我们可以通过增加空间占用的方式减少算法的运行时间，这便是空间换时间。

动态规划就是一类空间换时间的算法。动态规划通过保存所有子问题的计算结果，可以避免子问题的重复计算。这种方法的代价是 DP 数组 占用了较多的空间。

前缀和同样也是一种空间换时间的技巧，只不过我们使用的不是 DP 数组，而是「前缀和数组」。

那么，究竟什么是前缀和呢？

什么是前缀和

我们先用一道简单的题目理解一下「前缀和」究竟是做什么的：

LeetCode 303. Range Sum Query - Immutable（Easy）

给定一个整数数组  nums，求出数组从索引 到  () 范围内元素的总和，包含 、 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明：

• 假设数组不可变

• 会多次调用 sumRange 函数

这道题目的解法很直白，难点在于如何减少时间复杂度。我们来看看不同的解法的时间、空间复杂度有何区别。

解法一：暴力法

如果用暴力解法，每次调用 sumRange 时，都使用 for 循环将 到 之间的元素相加。

public int sumRange(int i, int j) {
    int sum = 0;
    for (int k = i; k <= j; k++) {
        sum += nums[k];
    }
    return sum;
}

这样的话，每次查询（即每次调用 sumRange）平均需要 的时间。由于 sumRange 函数会被多次调用，这种算法的时间开销会非常大。

解法二：空间换时间

在 sumRange 会被调用很多次的情况下，我们要尽可能地减少一次调用的时间。如果多次调用 sumRange 的参数是重复的，但还需要重新求和，就会做很多重复的计算。

为了避免重复的计算，我们可以对数组 nums 进行预处理，预先存储计算结果。我们使用二维数组 res 存储预处理的结果，res[i][j] 存储 sumRange(i, j) 的返回值。