前言

• 前缀和是一种非常适合处理 区间查询 问题的算法技巧，理解前缀和的思想对后续学习 线段树、字典树 很有帮助；
• 在这篇文章里，我将梳理前缀和的基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

目录

1. 前缀和 + 差分

首先，我们使用一道典型例题来引入前缀和的概念。

303. 区域和检索 - 数组不可变【题解】

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

这道题的暴力解法是很容易想到的，区间[i,j]的和无非就是累加区间元素即可，时间复杂度是O(n)，空间复杂度是O(1)。但如果多次检索区间[i,j][i, j][i,j]的和，暴力解法就显得不优雅了，因为暴力解法中存在 很多重复求和运算。举个例子，暴力解法计算区间[1,5]和区间[1,10]，区间[1,5]的元素就重复执行了求和运算。

那么，有没有办法优化区间和的时间复杂度呢？在 O(1)时间复杂度内计算[5000,1000000]的区间和，有可能吗？方法总是有的，无非是利用空间换取时间，这就需要使用「前缀和 + 差分」技巧了。

前缀和的基本套路是开辟一个前缀和数组，存储「元素所有前驱节点的和」，例如：

val sum = IntArray(nums.size + 1) { 0 }
for (index in nums.indices) {
    sum[index + 1] = sum[index] + nums[index]
}
复制代码

参考代码：

class NumArray(nums: IntArray) {
    private val sum = IntArray(nums.size + 1) { 0 }
    init {
        for (index in nums.indices) {
            sum[index + 1] = sum[index] + nums[index]
        }
    }
    fun sumRange(i: Int, j: Int): Int {
        return sum[j + 1] - sum[i] // 注意加一
    }
}
复制代码

提示： 前缀和数组长度不一定要比原数组长度大 1，加 1 的目的是为了在后面做差分的时候代码会比较简洁。

另外，前缀和还适用于二维区间和检索，思路都是类似的，你可以试试看：

304. 二维区域和检索 - 矩阵不可变【题解】

2. 前缀和 + 哈希表优化

这一节我们来讨论前缀和结合哈希表的优化技巧，这种技巧一般是适用在一些 只关心次数，不关心具体的解 的场景。利用哈希表 O(1)时间复杂度查询的特性，可以进一步优化时间复杂度。

同样地，我们使用一道典型例题来展开讨论：

560. 和为K的子数组【题解】

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

题目的要求是计算和为 k 的子数组个数，掌握了使用前缀和计算区间和后，我们可以轻松地写出一种解法：在这里我们枚举每个子数组，使用「前缀和 + 差分」技巧计算区间和为 kkk 的个数：

参考代码：

class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        1、预处理：构造前缀和数组
        var preSum = IntArray(nums.size + 1) { 0 }
        for (index in nums.indices) {
            preSum[index + 1] = preSum[index] + nums[index]
        }
        2、枚举所有子数组，使用「前缀和 + 差分」技巧计算区间和
        var result = 0
        for (i in nums.indices) {
            for (j in i until nums.size) {
                val sum_i_j = preSum[j + 1] - preSum[i]
                if (k == sum_i_j) {
                    result++
                }
            }
        }
        return result
    }
}
复制代码

整个算法的时间复杂度是O(n2)，空间复杂度是O(n)，这是最优算法了吗？因为题目要求的是数组个数，而不关心具体的数组，所以我们大可不必枚举全部子数组（一共有n2n^2n2个子数组），我们只需要在计算出当前位置的前缀和之后，观察之前位置符合条件的前缀和个数即可。

具体来说，对于当前位置已经计算出前缀和 ，我们只需要寻找在[0,j−1]区间内，前缀和为 的个数。

紧接着的问题是：怎么快速查找前缀和为preSum[j]−kpreSum[j] - kpreSum[j]−k 的个数呢？聪明的你一定知道是哈希表了，我们需要维护一个哈希表：Key 为前缀和，Value 为前缀和出现次数。

参考代码：

class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        var preSum = 0
        var result = 0
        维护一个哈希表：Key 为前缀和，Value 为前缀和出现次数
        val map = HashMap<Int, Int>()
        在索引 0 之前，存在一个前缀和为 0 的空数组
        map[0] = 1
        for (index in nums.indices) {
            preSum += nums[index]
            查询前缀和为 preSum - k 的个数
            val offset = preSum - k
            if (map.contains(offset)) {
                result += map[offset]!!
            }
            map[preSum] = map.getOrDefault(preSum, 0) + 1
        }
        return result
    }
}
复制代码

如此，整个算法的时间复杂度降低为O(n)O(n)O(n)，空间复杂度保持为O(n)O(n)O(n)。

3. 举一反三

525. 连续数组【题解】

1004. 最大连续1的个数 III

1248. 统计「优美子数组」

974. 和可被 K 整除的子数组

352. 和等于 K 的最长子数组长度

1314. 矩阵区域和

4. 总结

• 前缀和技巧适用于区间查询等问题，当问题中提到 “连续子数组” 时，可以考虑使用「前缀和 + 差分」技巧；
• 在只关心次数，不关心具体的解的场景，可以使用前缀和 + 哈希表进一步优化时间复杂度；
• 前面提到的问题都属于静态数据场景，也就是前缀和只需要计算一次即可。如果数据是动态的呢，还可以使用前缀和吗？你可以思考下这两道题。

307. 区域和检索 - 数组可修改

308. 二维区域和检索 - 矩阵不可变