【优选算法篇】前缀和与哈希表的完美结合：掌握子数组问题的关键（下篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

接上篇：【优选算法篇】解密前缀和：让数组求和变得如此高效（上篇）-CSDN博客

引言：通过上篇文章带大家简单了解“前缀和算法”，小试牛刀。接下来将让大家感受一下前缀和在解题的妙处。

• 常见问题举例： 在笔试中，常见的前缀和问题包括：
  • 区间求和问题：给定一个数组和多个查询区间，求每个区间的和。
  • 最大子数组和问题：在一个数组中，找出和最大的连续子数组。
  • 子数组和为固定值的数量：在一个数组中，求和为某个固定值的子数组的数量。
  • 子数组的和为 k 的倍数：通过前缀和和余数来判断某些特定条件的子数组。
• 节省时间和提升效率： 在笔试中，时间是非常宝贵的资源。通过使用前缀和算法，许多问题可以从 O(n^2) 或 O(n) 降到 O(1)，这对于解决大规模数据的题目非常重要。例如，一个数组大小为 100,000，如果没有前缀和的优化，直接计算区间和的时间复杂度可能会让你无法在规定时间内完成题目。

面试中的价值

• 普适性强：很多经典题目和复杂场景都可以通过前缀和简化。
• 体现逻辑与优化能力：面试官通过考察前缀和，评估候选人在算法设计和空间换时间的优化思路上的理解深度。
• 高效实现力：代码实现简洁高效，能够展示良好的编码能力。

前言

前缀和（Prefix Sum）算法在笔试中的重要性非常高，因为它能够极大地优化数组相关问题的时间复杂度，尤其是在涉及区间求和、子数组和等问题时。通过前缀和算法，许多看似复杂的算法问题都能得到高效解决，避免了暴力解法的时间瓶颈。

"前缀和算法：从基础到高级场景的全面解析"

1. C++ 前缀和算法 进阶详解

1.1 前缀和概念

前缀和（Prefix Sum） 是指一个数组的前缀部分元素的累加和。对于一个数组 arr，前缀和数组 prefix_sum 的定义为：

• prefix_sum[i] = arr[0] + arr[1] + ... + arr[i-1]，即数组从第一个元素到第 i 个元素的和。

1.2 经典应用

1. 子数组和查询
   • 使用前缀和可以快速计算任意区间 [l, r] 的和，时间复杂度为 O(1)。
   • 应用场景：当数组中有多个关于子数组和的查询时，预处理前缀和能显著提高性能。
2. 区间和频率统计
   • 在计算一个数组中符合某个条件的子数组数量时，前缀和与哈希表结合可以有效解决问题。例如，查找和为某个固定值 k 的子数组数量。
   • 应用场景：查找满足和为某个值的子数组个数，或者满足区间和与某个数的关系（如能被某个数整除）的子数组个数。
3. 前缀和与余数结合
   • 计算子数组和是否能被某个数整除时，可以结合前缀和与余数来进行优化。具体方法是通过哈希表记录各个前缀和的余数。
   • 应用场景：解决子数组和能否被 k 整除的问题，利用前缀和的余数减少不必要的重复计算。
4. 差分数组与前缀和结合
   • 在区间修改问题中，使用差分数组与前缀和结合可以在常数时间内更新一个区间的值，并且通过前缀和恢复最终结果。
   • 应用场景：动态更新数组的某个区间并查询该区间的和。

2. 题目1：和为k的子数组

题目链接：560. 和为 K 的子数组 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

1. 前缀和定义：
   • 前缀和是指数组从起点到当前位置的元素和。
   • 假设 sum[i] 表示数组从 nums[0] 到 nums[i] 的前缀和。
   • 那么，任何子数组 nums[i:j] 的和可以表示为： sum[j]−sum[i−1]=k 转化为： sum[j]−k=sum[i−1] 这说明，如果我们知道当前前缀和 sum[j] 和目标值 k，我们只需要找到之前某个前缀和 sum[i-1] 满足这个条件，就可以确定一个子数组的和为 k。
2. 哈希表的作用：
   • 用一个哈希表 hash 来记录每个前缀和出现的次数。
   • 键：前缀和的值 sum。
   • 值：该前缀和出现的次数 hash[sum]。
   • 在遍历数组时，每遇到一个新的前缀和 sum[j]，我们计算是否存在 sum[j] - k 在哈希表中。如果存在，说明有对应的子数组和等于 k，并将 hash[sum[j] - k] 的值累加到结果中。
3. 优化：
   • 我们可以一边遍历数组、一边更新当前前缀和和哈希表。
   • 无需重新计算每个子数组的和，时间复杂度从 O(n^2) 降低到 O(n)。

2.2 示例代码：

int subarraySum(vector<int>& nums, int k) 
{
    unordered_map<int, int> hash; // 哈希表记录前缀和及其出现次数
    hash[0] = 1; // 初始化：前缀和为 0 的情况出现 1 次（用于处理从头开始的子数组）

    int ret = 0, sum = 0; // ret：结果变量；sum：当前前缀和

    for (auto x : nums) // 遍历数组的每个元素
    {
        sum += x; // 更新当前前缀和

        // 检查是否存在满足条件的前缀和
        // 如果 `sum - k` 存在于哈希表中，说明从之前某位置到当前的子数组和为 k
        if (hash.count(sum - k)) 
            ret += hash[sum - k]; // 累加满足条件的子数组个数

        // 更新哈希表：记录当前前缀和 `sum` 出现的次数
        hash[sum]++;
    }

    return ret; // 返回结果
}

2.2.1 具体执行流程

假设 nums = [1, 1, 1]，k = 2：

最终返回结果：ret = 2 。

2.3 补充（可看可不看）

2.3.1 暴力解法

暴力解法的核心思路

• 枚举所有可能的子数组，计算其和。
• 如果某个子数组的和等于 k，则计数增加。
• 使用两层嵌套循环遍历所有子数组。

2.3.2 示例代码：

int subarraySum(vector<int>& nums, int k) 
{
    int n = nums.size(); // 数组长度
    int ret = 0; // 用于记录满足条件的子数组数量

    // 枚举子数组的起点
    for (int i = 0; i < n; i++) 
    {
        int sum = 0; // 当前子数组的和
        // 枚举子数组的终点
        for (int j = i; j < n; j++) 
        {
            sum += nums[j]; // 累加当前子数组的和
            if (sum == k) // 检查子数组和是否等于 k
                ret++; // 满足条件，结果加 1
        }
    }
    return ret; // 返回满足条件的子数组数量
}

2.3.2.1 运行流程举例

输入：nums = [1, 2, 3], k = 3

1. 初始化：
   • 数组长度 n = 3
   • 结果计数器 ret = 0
2. 第一层循环 (起点)：i = 0
   • 初始化 sum = 0
   • 第二层循环：
     • j = 0: sum = 0 + 1 = 1，不满足条件。
     • j = 1: sum = 1 + 2 = 3，满足条件，ret = 1。
     • j = 2: sum = 3 + 3 = 6，不满足条件。
3. 第一层循环 (起点)：i = 1
   • 初始化 sum = 0
   • 第二层循环：
     • j = 1: sum = 0 + 2 = 2，不满足条件。
     • j = 2: sum = 2 + 3 = 5，不满足条件。
4. 第一层循环 (起点)：i = 2
   • 初始化 sum = 0
   • 第二层循环：
     • j = 2: sum = 0 + 3 = 3，满足条件，ret = 2。

最终返回结果：ret = 2

2.3.3 时间复杂度分析

1. 两层嵌套循环：
   • 第一层循环遍历所有起点 i，有 n 次迭代。
   • 第二层循环从 i 开始，遍历所有终点 j，最坏情况下每次有 n−i 次迭代。
   • 总的时间复杂度为： T=n-1∑i=0​(n−i)=n(n+1)​/2=O(n2)
2. 空间复杂度：
   • 没有额外的数据结构，使用常数空间，空间复杂度为 O(1)。

2.3.4 优缺点

优点：

1. 思路简单，易于实现。
2. 无需额外的数据结构，代码直观。

缺点：

1. 效率低：时间复杂度为 O(n^2)，当 n 较大时性能不佳。
2. 适用于小规模问题，大规模数组时不推荐。

2.3.5 总结:

暴力解法适用于入门理解和小规模测试，但当数组规模较大时，应该优先选择优化解法（如前缀和 + 哈希表），将时间复杂度优化至 O(n)。

2.4 复杂度分析

1. 时间复杂度： O(n)
   • 每个元素遍历一次，哈希表的插入和查找都是 O(1),因此整体是线性的。
2. 空间复杂度： O(n)
   • 哈希表在最坏情况下可能存储 n 个不同的前缀和。

2.5 总结

这段代码通过前缀和和哈希表的结合，快速统计和为 k 的子数组个数，既高效又易于扩展，是面试中常见的算法技巧。

3. 题目2：和可被k整除的子数组

题目链接：974. 和可被 K 整除的子数组 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

算法核心思路

使用 前缀和 + 哈希表 来高效解决问题。

前缀和的数学推导

1. 定义前缀和为 sum[j]，表示数组从起点到位置 j 的元素和。
2. 子数组和为 sum[i:j]=sum[j]−sum[i−1]，其中 i 是子数组的起点，j 是终点。
3. 若要满足子数组和 sum[i:j]%k=0，则有： (sum[j]−sum[i−1])%k=0 转化为： sum[j]%k=sum[i−1]%k 这说明：
   • 如果两个前缀和的余数相同，则它们之间的子数组和可以被 k 整除。

哈希表的作用

• 使用哈希表记录每个余数出现的次数。
• 遍历数组时，计算当前前缀和的余数，若该余数已经出现在哈希表中，则说明存在子数组的和可以被 k 整除，子数组的个数等于当前余数在哈希表中出现的次数。

处理负余数的问题

• 为了确保余数为非负数（避免负数计算时出错），计算余数时统一使用： r=(sum%k+k)%k 这样可以将负余数调整到非负范围。

3.2 示例代码：

int subarraysDivByK(vector<int>& nums, int k) 
{
    unordered_map<int, int> hash; // 哈希表存储余数及其出现次数
    hash[0] = 1; // 初始条件：前缀和为 0 的余数情况，初始时存在 1 次
    int sum = 0, ret = 0; // sum 表示当前前缀和，ret 统计满足条件的子数组个数

    for (auto x : nums) // 遍历数组中的每个元素
    {
        sum += x; // 更新当前前缀和
        int r = (sum % k + k) % k; // 计算当前前缀和的余数，并保证非负
        if (hash.count(r)) // 如果当前余数已经存在于哈希表中
            ret += hash[r]; // 累加满足条件的子数组个数
        hash[r]++; // 更新当前余数的出现次数
    }
    return ret; // 返回结果
}

3.2.1 运行流程

示例：nums = [4, 5, 0, -2, -3, 1], k = 5

最终返回结果：ret = 7

3.3 补充（可看可不看）

3.3.1 暴力解法

暴力解法的核心思路

• 枚举所有可能的子数组，计算每个子数组的和。
• 判断当前子数组的和是否能被 k 整除。
• 如果能整除，则结果计数增加。

3.3.2 代码实现

int subarraysDivByK(vector<int>& nums, int k) 
{
    int n = nums.size(); // 数组长度
    int ret = 0; // 记录满足条件的子数组数量

    // 枚举所有子数组的起点
    for (int i = 0; i < n; i++) 
    {
        int sum = 0; // 子数组的和
        // 枚举子数组的终点
        for (int j = i; j < n; j++) 
        {
            sum += nums[j]; // 累加当前子数组的和
            if (sum % k == 0) // 检查是否能被 k 整除
                ret++; // 如果满足条件，计数加 1
        }
    }
    return ret; // 返回结果
}

3.3.3 运行流程举例

示例输入：nums = [4, 5, 0, -2, -3, 1], k = 5

1. 外层循环：起点从 i = 0 到 i = n - 1。
2. 内层循环：从当前起点开始累加子数组的和，检查是否能被 kkk 整除。

运行细节如下：

最终，统计到的满足条件的子数组数量为 7。

3.3.4 时间复杂度分析

两层嵌套循环：

• 外层循环遍历子数组的起点 i，共 n 次。
• 内层循环遍历从 i 开始的子数组终点 j，最多执行 n−i次。
• 总的时间复杂度为：T= i=0∑n−1​(n−i)=2n(n+1)​=O(n2)

空间复杂度：

• 没有使用额外的数据结构，空间复杂度为 O(1)。

3.3 5 优缺点分析

优点：

1. 简单直观：直接通过两层嵌套枚举所有子数组，思路清晰，便于理解。
2. 适用于小规模数据：当数组长度 n 较小时，性能尚可。

缺点：

1. 性能较差：时间复杂度为 O(n^2)，对于大规模数组（如 n > 10^4）效率较低。
2. 重复计算：每次都从头计算子数组的和，未利用前缀和等优化手段。

3.3.6 适用场景

• 数据规模较小（如 n≤1000）时，暴力解法是快速实现的选择。
• 用于入门理解问题的性质与约束条件，为进一步优化提供基础。

优化方向

1. 前缀和 + 哈希表：
   • 利用前缀和的性质，将时间复杂度优化到 O(n)。
2. 滑动窗口：
   • 对于正数数组，可以通过滑动窗口优化。
3. 动态规划：
   • 在特殊情况下（如固定 k 或正整数数组），可用动态规划优化子数组和的计算。

暴力解法虽简单直观，但对于大规模数据难以满足性能要求，因此在实际应用中更推荐使用优化解法。

3.4 时间和空间复杂度分析

3.4.1 时间复杂度

• 遍历数组一次，时间复杂度为 O(n)。
• 哈希表的插入和查询操作都是 O(1)。
• 总时间复杂度为 O(n)。

3.4.2 空间复杂度

• 哈希表存储最多 k个余数，空间复杂度为 O(k)。

回顾：代码中的重要点

1. 余数的非负化：
   • 使用 (sum%k+k)%k 来处理负数情况，保证余数始终为非负。
2. 哈希表初始值：
   • 将 hash[0] 初始化为 1，表示前缀和刚好等于 k 倍数的情况（例如从数组开头开始的子数组）。

3.5 总结：

1. 算法思路：
   • 借助前缀和与余数的性质，将问题转化为寻找余数相同的前缀和。
   • 使用哈希表存储余数出现的次数，快速统计满足条件的子数组。
2. 时间和空间效率高：
   • 通过优化，时间复杂度降为 O(n)，空间复杂度为 O(k)。
3. 适用场景：
   • 本算法可以高效解决模 k 问题的子数组统计，是模运算问题的经典解法之一。

4. 题目3：连续数组

题目链接：525. 连续数组 - 力扣（LeetCode）

题目描述：

4.1 算法思路

这道题的目标是求数组中连续子数组的最大长度，使得这个子数组中包含相等数量的 0 和 1。问题可以转化为找出具有相同前缀和的两个下标之间的最大距离。

核心思路：

1. 将问题转化为前缀和问题：
   • 遍历数组时，将 0 看作 -1，那么子数组中 0 和 1 的个数相等可以转换为前缀和为 0的情况。
   • 我们维护一个变量 sum 来记录从数组开始到当前位置的前缀和。
2. 使用哈希表记录前缀和的位置：
   • 使用一个哈希表 hash 存储前缀和及其第一次出现的位置。
   • 如果在后续遍历过程中发现相同的前缀和，说明从哈希表中存储的位置到当前的位置之间的子数组的和为 0（因为前缀和相同，说明中间部分抵消了）。
3. 计算最大长度：
   • 当发现相同的前缀和时，当前下标 i 减去哈希表中存储的对应前缀和的第一次出现的位置 hash[sum]，即可得到一个符合条件的子数组长度。
   • 维护一个变量 ret，更新最大长度。

4.2 示例代码：

class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        // 创建一个哈希表，用于存储前缀和及其第一次出现的位置
        unordered_map<int, int> hash;
        hash[0] = -1; // 初始值：假设在下标 -1 之前前缀和为 0
        
        int sum = 0; // 用于记录当前的前缀和
        int ret = 0; // 用于记录结果，即最大长度
        
        // 遍历数组
        for(int i = 0; i < nums.size(); i++)
        {
            // 更新前缀和：遇到 0 视为 -1，遇到 1 视为 +1
            sum += nums[i] == 0 ? -1 : 1;
            
            // 如果当前前缀和已经在哈希表中
            if(hash.count(sum)) 
            {
                // 计算从之前存储的位置到当前的位置的子数组长度
                ret = max(ret, i - hash[sum]);
            }
            else 
            {
                // 如果前缀和第一次出现，记录其位置
                hash[sum] = i;
            }
        }
        return ret; // 返回最大长度
    }
};

4.2.1 代码解析

关键变量：

1. sum：当前的前缀和。
2. hash：记录前缀和第一次出现的位置。
   • 初始值 hash[0] = -1 是为了处理整个数组的前缀和正好为 0 的情况。
3. ret：存储结果，即最大长度。

4.2.2 算法流程：

1. 初始化哈希表 hash，令 hash[0] = -1，代表从起始位置开始前缀和为 0。
2. 遍历数组 nums，每次遇到 1，将 sum 加 1；每次遇到 0，将 sum 减 1。
3. 检查当前 sum 是否已经存在于哈希表中：
   • 存在：计算子数组长度 i - hash[sum]，更新 ret。
   • 不存在：将当前 sum 记录到哈希表，值为当前下标 i。
4. 返回结果 ret。

示例分析

示例 1：

输入：nums = [0, 1]

• 初始：hash = {0: -1}, sum = 0, ret = 0
• 第 1 步：i = 0, nums[i] = 0 → sum = -1
  • hash = {0: -1, -1: 0}
• 第 2 步：i = 1, nums[i] = 1 → sum = 0
  • 找到 sum = 0 在 hash 中，计算长度 1 - (-1) = 2
  • 更新 ret = 2
• 最终结果：ret = 2

示例 2：

输入：nums = [0, 1, 0]

• 初始：hash = {0: -1}, sum = 0, ret = 0
• 第 1 步：i = 0, nums[i] = 0 → sum = -1
  • hash = {0: -1, -1: 0}
• 第 2 步：i = 1, nums[i] = 1 → sum = 0
  • 找到 sum = 0 在 hash 中，计算长度 1 - (-1) = 2
  • 更新 ret = 2
• 第 3 步：i = 2, nums[i] = 0 → sum = -1
  • 找到 sum = -1 在 hash 中，计算长度 2 - 0 = 2
  • ret 不变。
• 最终结果：ret = 2

4.3 补充（可看可不看）

4.3.1 暴力解法

暴力解法算法思路

1. 定义子数组：
   • 任意子数组由两个下标 i 和 j 确定，子数组为 nums[i:j+1]。
   • 我们需要检查这个子数组中 0 和 1 的数量是否相等。
2. 枚举所有可能的子数组：
   • 遍历数组的起点 i。
   • 对于每个起点 i，再遍历终点 j，即子数组范围 [i, j]。
3. 统计 0 和 1 的数量：
   • 遍历子数组 [i, j]，统计其中的 0 和 1 的数量。
   • 如果 0 和 1 的数量相等，则更新最大长度。
4. 返回最大长度：
   • 遍历完成后，返回记录的最大长度。

4.3.2 实现代码

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int maxLength = 0; // 记录最大长度
        
        // 枚举子数组的起点
        for (int i = 0; i < nums.size(); i++) {
            int count0 = 0, count1 = 0; // 统计 0 和 1 的数量
            
            // 枚举子数组的终点
            for (int j = i; j < nums.size(); j++) {
                if (nums[j] == 0) count0++; // 统计 0
                else count1++;              // 统计 1
                
                // 如果 0 和 1 的数量相等，更新最大长度
                if (count0 == count1) {
                    maxLength = max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
};

示例解析

示例 1：

输入：nums = [0, 1]

1. 枚举子数组：
   • [0]：count0 = 1, count1 = 0 → 不满足条件。
   • [1]：count0 = 0, count1 = 1 → 不满足条件。
   • [0, 1]：count0 = 1, count1 = 1 → 满足条件，更新最大长度 maxLength = 2。

输出：2

示例 2：

输入：nums = [0, 1, 0]

1. 枚举子数组：
   • [0]：count0 = 1, count1 = 0 → 不满足条件。
   • [1]：count0 = 0, count1 = 1 → 不满足条件。
   • [0, 1]：count0 = 1, count1 = 1 → 满足条件，maxLength = 2。
   • [0, 1, 0]：count0 = 2, count1 = 1 → 不满足条件。
   • [1, 0]：count0 = 1, count1 = 1 → 满足条件，maxLength = 2。

输出：2

4.3.3 时间和空间复杂度

1. 时间复杂度：O(n²)
   • 枚举起点 i 和终点 j 的两层循环，时间复杂度为 O(n²)。
   • 对每个子数组计算 0 和 1 的数量，时间复杂度为 O(1)。
   • 总时间复杂度为 O(n²)。
2. 空间复杂度：O(1)
   • 仅使用常量额外空间。

4.3.4 优点和缺点

优点：

• 实现简单，易于理解。
• 直接暴力枚举，不需要额外的数据结构。

缺点：

• 效率低：当数组较大时，O(n²) 的时间复杂度会导致超时。
• 无法处理超长数组：对于大规模输入，不具备实际可行性。

对比优化方法

暴力解法虽然可以解决问题，但在性能上远不及优化方法（如利用前缀和与哈希表的解法）。优化后的方法可以将时间复杂度降到 O(n)，在 LeetCode 算法平台上更适合处理大规模输入。

4.4 总结：

通过将问题转化为前缀和的寻找，我们能够在 O(n) 时间复杂度内高效解决这类问题。

5. 题目4：矩阵区域和

题目链接：1314. 矩阵区域和 - 力扣（LeetCode）

题目描述：

5.1 算法思路：

核心思路

1. 二维前缀和：
   • 我们定义一个二维前缀和数组 dp，其中 dp[i][j] 表示从矩阵左上角 (0, 0) 到位置 (i-1, j-1) 的子矩阵的所有元素之和。
   • 公式： dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]+mat[i−1][j−1]
   • 这样，任意矩形区域 (x1, y1) 到 (x2, y2) 的和可以快速通过前缀和计算： Sum=dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]+dp[x1−1][y1−1]
2. 块和的计算：
   • 对于矩阵中的每个位置 (i, j)，需要求以该位置为中心，大小为 k 的块内所有元素的和。
   • 我们通过前缀和快速计算，避免直接遍历整个块：
     • 块的左上角坐标为：(max(0, i-k), max(0, j-k))
     • 块的右下角坐标为：(min(n-1, i+k), min(m-1, j+k))
   • 计算时，将坐标转换为 dp 数组的索引，注意处理越界。

5.2 代码实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size();       // 矩阵的行数
        int m = mat[0].size();    // 矩阵的列数

        // 计算二维前缀和数组 dp
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        // 计算结果矩阵 ret
        vector<vector<int>> ret(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 块的左上角和右下角坐标
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(n - 1, i + k) + 1, y2 = min(m - 1, j + k) + 1;

                // 利用前缀和快速计算块和
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }

        return ret;
    }
};

5.2.1 代码解析

1. 前缀和的计算

for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1]; } }

• dp[i][j] 代表从矩阵左上角到位置 (i-1, j-1) 的矩形的元素和。
• 前缀和公式：
  • 加上当前行之前的前缀和：dp[i - 1][j]
  • 加上当前列之前的前缀和：dp[i][j - 1]
  • 减去重复计算的部分：dp[i - 1][j - 1]
  • 加上当前元素值：mat[i - 1][j - 1]

2. 块和的计算

int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1; int x2 = min(n - 1, i + k) + 1, y2 = min(m - 1, j + k) + 1; ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];

• 块范围的处理：
  • 使用 max 和 min 确保块范围不越界。
  • 转换为前缀和索引（+1 是因为 dp 数组比矩阵大一维）。
• 利用前缀和计算块和：
  • 使用公式快速计算矩形区域的和。

5.3 补充（可看可不看）

5.3.1 暴力解法

1. 枚举每个元素：
   • 遍历矩阵中每个位置 (i, j)。
2. 计算块和：
   • 对于位置 (i, j)，枚举大小为 k 的块中的所有元素。
   • 块的范围由：
     • 行范围：[max(0, i-k), min(n-1, i+k)]
     • 列范围：[max(0, j-k), min(m-1, j+k)]
   • 在该范围内直接累加所有元素。
3. 记录结果：
   • 将计算得到的块和存储在结果矩阵 ret 中。
4. 返回结果：
   • 遍历完成后，返回 ret。

5.3.2 实现代码

以下是暴力解法的实现代码：

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size();       // 矩阵的行数
        int m = mat[0].size();    // 矩阵的列数
        
        vector<vector<int>> ret(n, vector<int>(m, 0)); // 结果矩阵
        
        // 遍历每个元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 枚举块的范围
                int sum = 0;
                for (int x = max(0, i - k); x <= min(n - 1, i + k); x++) {
                    for (int y = max(0, j - k); y <= min(m - 1, j + k); y++) {
                        sum += mat[x][y]; // 累加块中的元素
                    }
                }
                ret[i][j] = sum; // 记录结果
            }
        }
        return ret;
    }
};

5.3.3 复杂度分析

时间复杂度

总复杂度分析：

1. 外层循环：
   • 遍历矩阵的每个位置 (i, j)，需要 O(n × m)。
2. 内层循环：
   • 对于每个位置 (i, j)，枚举大小为 k 的块范围。
   • 块范围最多包含 (2k+1) × (2k+1) 个元素。
   • 枚举块的复杂度为 O(k²)。
3. 总复杂度：
   • 时间复杂度为 O(n × m × k²)。

空间复杂度：

• 结果矩阵 ret 和输入矩阵 mat 的大小均为 O(n × m)，不使用额外存储。
• 空间复杂度为 O(n × m)。

5.3.4 优点和缺点

优点：

1. 实现简单，直接按照题意逐步累加，适合入门理解。
2. 不需要额外的数据结构或预处理。

缺点：

1. 效率低：
   • 当 k 较大时，计算复杂度会大幅上升（O(n × m × k²)），导致超时。
2. 不可扩展：
   • 对于矩阵规模较大或 k 值较大的情况，无法在合理时间内完成计算。

5.3.5 优化方向

为了提高效率，可以通过以下优化方案：

1. 前缀和：
   • 预处理一个二维前缀和数组，快速计算任意矩形区域的和，降低块和计算的复杂度。
   • 时间复杂度优化为 O(n × m)。
2. 滑动窗口：
   • 对于较小的矩阵，可以通过滑动窗口法动态调整块范围的和。

5.3.6 总结

暴力解法虽然直观易于理解，但性能不佳，仅适用于小规模数据。在实际应用中，前缀和的优化方法是解决该题目的最佳方案。

5.4 复杂度分析

5.4.1 时间复杂度

1. 前缀和的计算：
   • 遍历整个矩阵，时间复杂度为 O(n × m)。
2. 块和的计算：
   • 遍历每个位置 (i, j)，时间复杂度为 O(n × m)。
   • 由于前缀和查询是 O(1)，总复杂度不会增加。

总时间复杂度：O(n × m)

5.4.2 空间复杂度

• 使用了一个二维前缀和数组 dp，大小为 (n+1) × (m+1)。
• 额外使用一个结果数组 ret，大小为 n × m。

总空间复杂度：O(n × m)

5.5 总结

通过二维前缀和优化，我们在 O(n × m) 的时间复杂度内完成了矩阵块和的计算，极大提高了效率。

6.总结：

前缀和是处理区间问题的基础工具，它能有效地优化数组相关问题的查询时间。通过预处理前缀和数组，我们能够将查询区间和的时间复杂度从 O(n) 降到 O(1)。进阶应用中，前缀和常与哈希表、余数、差分数组等技术结合使用，解决更多复杂的问题。掌握前缀和的基础与进阶技巧，是提高算法效率、应对复杂问题的重要步骤。

7. 最后

通过上面几个例题：「矩阵块和」的暴力解法与优化解法、「连续数组」的前缀和应用，以及**「查找数组中平衡块」的二维前缀和方法。 前缀和算法通过将复杂的重复计算问题转化为简单的加减法，极大地提升了问题求解的效率。在处理数组或矩阵中的区间求和、动态范围查询等问题时，表现出显著的性能优势，特别适用于大规模数据的应用场景。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！