3263 字
16 分钟
前缀和数组
2025-08-23
算法
前缀和

前缀和#

定义#

  • 前缀和是一种数据结构优化技术，通过预先计算并存储数组从起始位置到每个位置的累积和，使得任意区间和的查询可以在O(1)时间内完成。具体来说，对于数组 a[0…i]，前缀和数组 prefix[i + 1] = a[0] + a[1] + … + a[i]，这样区间 [i, j] 的和就等于 prefix[j + 1] - prefix[i]。

适用场景#

  • 前缀和适用于快速、频繁地计算一个索引区间内的元素之和。但前提要求是数组的元素在查询过程中不能被修改，以及只适用于支持逆运算的场景。
    • 为什么要求数组的元素在查询过程中不能被修改？
      • 因为前缀和数组是基于原始数组构建的，如果原始数组的元素被修改，前缀和数组中的值也需要相应地更新。
    • 什么是逆运算？以及为什么只适用于支持逆运算场景？
      • 逆运算是指通过已知的结果反推输入的过程，比如：你知道 x + 6 = 10，那么可以推导出 x = 10 - 6 = 4。前缀和通过差值计算区间和，需要运算支持逆运算（如加法的逆运算是减法）。
  • 如何判断当前场景是否适合使用前缀和？
    • 如果需要频繁查询某个区间的和，并且在查询过程中数组的元素不会被修改，那么可以考虑使用前缀和。
  • 前缀和的变种，比如在一个只有0和1的数组中，计算相同数量的 0 和 1 的最长连续子数组。这时候可以将 0 替换为 -1，然后使用前缀和来解决问题。
  • 当在前缀和中出现了需要查找的值时，可以使用哈希表来存储前缀和第一次出现的位置，从而在遍历时快速查找。

前缀和配合不同数据结构的使用场景#

1. 需要使用双for循环的情况#

特征：需要计算所有位置/所有子数组的结果

典型例子：

  • 矩阵区域和：需要计算矩阵中每个位置的区域和
  • 除自身以外数组的乘积：需要计算每个位置的结果

这类题目的特点：

  • 结果是一个与原数组同样大小的数组
  • 每个位置都需要独立计算
  • 不涉及”查找满足条件的子数组”，而是”计算每个位置的值”

2. 构建完前缀和后，再遍历存入map的情况#

特征：需要找最长/最短的满足条件的子数组

典型例子：

  • 连续数组：找最长的0和1数量相等的子数组
  • 连续的子数组和：找是否存在长度至少为2且和为k倍数的子数组
# 典型模式
for i in range(n + 1):
    if pre[i] not in map:
        map[pre[i]] = i  # 只记录第一次出现的位置
    else:
        res = max(res, i - map[pre[i]])  # 计算长度

这类题目的特点：

  • 需要记录某个值第一次出现的位置
  • 目标是优化长度（最长/最短）
  • 需要比较不同位置的前缀和来确定最优解

3. 构建前缀和时同时维护map的情况#

特征：需要统计数量/计数

典型例子：

  • 和为K的子数组：统计和为k的子数组个数
  • 和可被K整除的子数组：统计和能被k整除的子数组个数
# 典型模式
for i in range(1, n + 1):
    pre[i] = pre[i-1] + nums[i-1]
    need = pre[i] - k  # 或其他条件
    if need in count:
        res += count[need]  # 累加数量
    count[pre[i]] = count.get(pre[i], 0) + 1  # 更新出现次数

这类题目的特点：

  • 需要统计满足条件的子数组数量
  • 不关心长度，只关心出现次数
  • 需要累加所有满足条件的情况

总结规律#

场景使用方式关键词map存储内容
计算每个位置的值双for循环”每个位置”、“返回数组”不需要map
找最优长度先构建前缀和，再遍历map”最长”、“最短”、“是否存在”值→第一次出现的索引
统计数量边构建边维护map”个数”、“数目”、“统计”值→出现次数

前缀和模板#

def build_prefix_sum(arr):
    n = len(arr)
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
    return prefix_sum


def query_range_sum(prefix_sum, left, right):
    return prefix_sum[right + 1] - prefix_sum[left]

二维数组的前缀和模板#

  • 当需要频繁查询一个二维区域的和时，可以使用二维前缀和。
  • 计算在[row1, col1]到[row2, col2]的区域和
def build_2d_prefix_sum(matrix):
    if not matrix or not matrix[0]:
        return []
    rows, cols = len(matrix), len(matrix[0])
    prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            prefix_sum[i][j] = (matrix[i - 1][j - 1]
                                + prefix_sum[i - 1][j]
                                + prefix_sum[i][j - 1]
                                - prefix_sum[i - 1][j - 1])
    return prefix_sum


def query_2d_range_sum(prefix_sum, row1, col1, row2, col2):
    return (prefix_sum[row2 + 1][col2 + 1]
            - prefix_sum[row1][col2 + 1]
            - prefix_sum[row2 + 1][col1]
            + prefix_sum[row1][col1])

例题解析#

  • 1314.矩阵区域和 LeetCode
    • 给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： i - k <= r <= i + k, j - k <= c <= j + k 且 (r, c) 在矩阵内。
    • 思路解析
      • 这题目就是计算距离自己一个单位范围内的和，简单来说就是当一个m x n的矩阵中,k = 1，计算mat[0][0]的值，就需要计算 0 - k <= x <=0 + k和0 - k <= x <=0 + k 范围内的和，也就是mat[0][0]到mat[1][1]范围内的所有元素之和。就相当于使用前缀和的思路，prefix_sum[2][2] - prefix_sum[0][2] - prefix_sum[2][0] + prefix_sum[0][0]。
    • 代码实现
    class Solution:
        def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
            m, n = len(mat), len(mat[0])
            pre_sum = [[0] * (n + 1) for _ in range(m + 1)]
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    pre_sum[i][j] = pre_sum[i - 1][j] + pre_sum[i][j - 1] + mat[i - 1][j - 1] - pre_sum[i - 1][j - 1]
            res = [[0] * n for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    row1, col1, row2, col2 = i - k, j - k, i + k, j + k
                    if i + k >= m:
                        row2 = m - 1
                    if j + k >= n:
                        col2 = n - 1
                    if i - k < 0:
                        row1 = 0
                    if j - k < 0:
                        col1 = 0
                    res[i][j] = pre_sum[row2 + 1][col2 + 1] - pre_sum[row2 + 1][col1] - pre_sum[row1][col2 + 1] + pre_sum[row1][col1]
            return res
  • 238.除自身以外数组的乘积 LeetCode
    • 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
    • 思路解析
      • 这道题可以使用前缀积和后缀积的思路来解决。我们可以先计算出每个元素左侧所有元素的乘积（前缀积），再计算每个元素右侧所有元素的乘积（后缀积），最后将前缀积和后缀积相乘得到结果。
    • 代码实现
    class Solution:
        def productExceptSelf(self, nums: List[int]) -> List[int]:
            n = len(nums)
            pre = [1] * n
            end = [1] * n
            for i in range(1, n):
                pre[i] = pre[i - 1] * nums[i - 1]
            for i in range(n - 2, -1, -1):
                end[i] = end[i + 1] * nums[i + 1]
            res = [0] * n
            for i in range(n):
                res[i] = pre[i] * end[i]
            return res
  • 1352.最后K个数的乘积 LeetCode
    • 设计一个算法，该算法接受一个整数流并检索该流中最后 k 个整数的乘积。实现 ProductOfNumbers 类：ProductOfNumbers() 用一个空的流初始化对象。void add(int num) 将数字 num 添加到当前数字列表的最后面。int getProduct(int k) 返回当前数字列表中，最后 k 个数字的乘积。你可以假设当前列表中始终 至少 包含 k 个数字。题目数据保证：任何时候，任一连续数字序列的乘积都在 32 位整数范围内，不会溢出。
    • 思路解析
      • 这道题可以使用前缀积的思路来解决。我们可以维护一个前缀积数组，前缀积数组的第 i 个元素表示当前数字列表中前 i 个数字的乘积。每次添加新数字时，我们只需要更新前缀积数组即可。在查询最后 k 个数字的乘积时，我们可以直接返回前缀积数组中第 k 个元素的值。
      • 另外需要判断当前数字是否为 0，如果为 0，则需要重置前缀积数组。
    • 代码实现
    class ProductOfNumbers:
        def __init__(self):
            self.pre = [1]
        def add(self, num: int) -> None:
            if num == 0:
                self.pre = [1]
                return
            self.pre.append(self.pre[-1] * num)
        def getProduct(self, k: int) -> int:
            if k >= len(self.pre):
                return 0
            return self.pre[-1] // self.pre[-k-1]
  • 525.连续数组 LeetCode
    • 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
    • 思路解析
      • 这道题可以使用前缀和的思路来解决。我们可以将 0 替换为 -1，然后求出前缀和。这样就转化为求出前缀和为 0 的最长子数组的长度。
      • 另外，我们可以使用哈希表来存储前缀和第一次出现的位置，从而在遍历时快速查找。
      • 当前缀和相等时，说明中间的子数组的 0 和 1 的数量相等。
    • 代码实现
    class Solution:
        def findMaxLength(self, nums: List[int]) -> int:
            n = len(nums)
            pre = [0] * (n + 1)
            for i in range(1, n + 1):
                pre[i] = pre[i - 1] + (1 if nums[i - 1] == 1 else -1)
            count = {}
            res = 0
            for i in range(n + 1):
                if pre[i] not in count:
                    count[pre[i]] = i
                else:
                    res = max(res, i - count[pre[i]])
            return res
  • 523.连续的子数组和 LeetCode
    • 给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：一个 好的子数组 是：长度 至少为 2 ，且子数组元素总和为 k 的倍数。注意：子数组 是数组中 连续 的部分。如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。
    • 思路解析
      • 这道题求连续子数组的和，就明显在提示你使用前缀和来解决。另外为了防止使用两个for循环来遍历，我们可以使用哈希表来存储前缀和的余数。当前缀和的余数相同时，说明中间的子数组的和是 k 的倍数。
    • 代码实现
    class Solution:
        def checkSubarraySum(self, nums: List[int], k: int) -> bool:
            n = len(nums)
            pre = [0] * (n + 1)
            for i in range(1, n + 1):
                pre[i] = pre[i - 1] + nums[i - 1]
            count = {}
            for i in range(n + 1):
                val = pre[i] % k
                if val not in count:
                    count[val] = i
    

            for i in range(1, n + 1):
                val = pre[i] % k
                if val in count:
                    if i - count[val] >= 2:
                        return True
            return False
  • 560.和为 K的子数组 LeetCode
    • 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
    • 思路解析
      • 在这道题中，我们可以使用前缀和的思路来解决。这里需要求的是前缀和等于 k 的子数组的个数。所以我们维护了一个哈希表，存储前缀和出现的次数。每次计算出当前的前缀和时，我们检查哈希表中是否存在前缀和等于当前前缀和减去 k 的值，如果存在，则说明找到了一个和为 k 的子数组。
    • 代码实现
    class Solution:
        def subarraySum(self, nums: List[int], k: int) -> int:
            n = len(nums)
            pre = [0] * (n + 1)
            count = {0: 1}
            res = 0
            for i in range(1, n + 1):
                pre[i] = pre[i - 1] + nums[i - 1]
                need = pre[i] - k
                if need in count:
                    res += count[need]
                if pre[i] not in count:
                    count[pre[i]] = 1
                else:
                    count[pre[i]] += 1
            return res
  • 974.和可被K整除的子数组 LeetCode
    • 给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。
    • 思路解析
      • 在这道题中，我们可以使用前缀和的思路来解决。这里的需求是找到和为 k 的倍数的子数组，因此我们可以使用哈希表来存储前缀和的余数。
      • 当前缀和的余数相同时，说明中间的子数组的和是 k 的倍数。
    • 代码实现
    class Solution:
        def subarraysDivByK(self, nums: List[int], k: int) -> int:
            n = len(nums)
            pre = [0] * (n + 1)
            counts = {0 : 1}
            res = 0
            for i in range(1, n + 1):
                pre[i] = pre[i - 1] + nums[i - 1]
                val = pre[i] % k
                if val < 0:
                    val += k
                if val in counts:
                    count = counts[val]
                    res += count
                    counts[val] += 1
                else:
                    counts[val] = 1
            return res
前缀和数组
https://fuwari.vercel.app/posts/prefix_array/
作者
Jarrett
发布于
2025-08-23
许可协议
CC BY-NC-SA 4.0
MySQL与Redis核心知识点
Go 性能分析与优化
© 2025 Jarrett. All Rights Reserved. / RSS / Sitemap