C++ 前缀和详解：进阶题解与思维分析

💬 欢迎讨论：如有疑问或见解，欢迎在评论区留言互动。

👍 点赞、收藏与分享：如觉得这篇文章对您有帮助，请点赞、收藏并分享！
🚀 分享给更多人：欢迎分享给更多对 C++ 感兴趣的朋友，一起学习前缀和的基础与进阶！

前言

在前一篇文章中，我们讨论了前缀和的基本概念及其基础应用，展示了如何利用前缀和快速解决数组区间求和问题。在这篇文章中，我们将继续深入探讨前缀和的更多应用，尤其是在解决一些中级难度问题中的实用性和效率提升。

第二章：前缀和进阶应用

2.1 和为 k 的子数组（medium）

题目链接：560. 和为 K 的子数组

题目描述：

给你一个整数数组 nums和一个整数 k，请你统计并返回该数组中和为 k的连续子数组的个数。

示例 1：

• 输入：nums = [1,1,1], k = 2
• 输出：2
• 解释：共有两个子数组的和为 2，分别是 [1,1]和 [1,1]。

示例 2：

• 输入：nums = [1,2,3], k = 3
• 输出：2
• 解释：共有两个子数组的和为 3，分别是 [1,2]和 [3]。

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

解法一（前缀和 + 哈希表）

算法思路：

我们可以通过划分所有以 i为结尾的子数组，逐步计算这些子数组的和是否为 k。如果满足条件，则累加结果。

1. 外层循环（枚举所有以 i结尾的子数组）：

   • 针对每一个位置 i，我们寻找与其满足和为 k的连续子数组。

2. 查找条件：

   • 要使 t-i的子数组和为 k，相当于找到位置 0-t-1的和为 sum - k。
   • 通过累加 0-i的前缀和 sum[i]，我们可以将此问题简化为查找 sum[i] - k是否在 0-t-1区间内存在。

3. 初始化 hash[0] = 1：

   • 这里的 hash[0] = 1是为了在 t=0时处理特殊情况。
   • 假设 t=0，即从数组的开始到 i位置的子数组和为 k，这等价于查找从 0-t-1的前缀和为 0。但 t=0时，区间 0-t-1为无效区间，因此初始化 hash[0] = 1可以保证从起点开始的累加和为 k。

示例分析

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

1. 初始状态：hash[0] = 1
2. 遍历 nums数组：
   • 第一次循环：sum = 1，在 hash中记录 hash[1] = 1
   • 第二次循环：sum = 3，此时 sum - k = 0存在于 hash，累积结果 ret = 1
   • 第三次循环：sum = 6，此时 sum - k = 3存在于 hash，累积结果 ret = 2

最终结果为 2，即子数组 [1, 2]和 [3]满足和为 k。

C++代码实现

classSolution{ public:intsubarraySum(vector<int>&nums,intk){ unordered_map<int,int>hash;// 记录前缀和出现的次数hash[0]=1;// 确保能统计到从起点到i的子数组和为k的情况intsum =0,ret =0;for(autox :nums){ sum +=x;// 计算当前前缀和if(hash.count(sum -k))ret +=hash[sum -k];// 统计符合条件的前缀和个数hash[sum]++;// 更新前缀和出现次数}returnret;}};

易错点提示

1. 哈希表初始化：

   • hash[0] = 1是关键，确保统计从数组起点到 i的子数组和为 k的情况。

2. 前缀和更新顺序：

   • 遍历过程中，计算 sum后先查找 hash[sum - k]，再更新 hash[sum]。

3. 返回值累加逻辑：

   • 查询 hash[sum - k]的值并累加至 ret，每次查找到的值直接反映了符合条件的子数组数量。

代码解读

通过使用哈希表存储前缀和出现的次数，我们可以在一次遍历中快速找到和为 k的子数组个数。

• 时间复杂度：O(n)，因为只需遍历数组一次。
• 空间复杂度：O(n)，最坏情况下，每个前缀和都唯一，存入哈希表。

2.2 和可被 K 整除的子数组（medium）

题目链接：974. 和可被 K 整除的子数组

题目描述：

给定一个整数数组 nums和一个整数 k，返回其中元素之和可被 k整除的（连续、非空）子数组的数目。

示例 1：

• 输入：nums = [4,5,0,-2,-3,1], k = 5
• 输出：7
• 解释：共有 7 个子数组满足其元素之和可被 k = 5整除：
  • [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2：

• 输入：nums = [5], k = 9
• 输出：0

提示：

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• 2 <= k <= 10^4

解法（前缀和 + 哈希表 + 同余定理）

算法思路：

目标是统计出和为 k的倍数的子数组数量。通过利用前缀和和同余定理可以实现线性复杂度的解法：

1. 同余定理：
   两个数如果相减的差能够被 k整除，则它们的余数相同，即 (a - b) % k == 0等价于 a % k == b % k。
   因此，只要在遍历过程中，当前位置前缀和与之前某个前缀和的余数相同，即可认为它们之间的子数组和能被 k整除。

2. 前缀和与余数的关系：

   • 用 sum[i]表示从数组起始位置到 i的累加和。对于位置 i，要找到多少个以 i结尾且和可被 k整除的子数组，就需要查找在 0到 i-1区间内，前缀和对 k取余与 sum[i] % k相同的前缀和出现次数。

3. 哈希表记录余数出现次数：

   • 通过哈希表 hash存储每种余数的出现次数，遍历时如果 sum % k在 hash中出现过，表示到当前位置 i存在相同余数的前缀和，可以形成满足条件的子数组。
   • 每次找到余数相同的前缀和时，将其次数累加到结果中，然后更新 hash。

4. 处理负数余数：

   • 在某些编程语言中（如 C++），负数取模保留负号。为了避免负数影响判断，我们将余数调整为非负，表达式为 (sum % k + k) % k。

详细示例

假设 nums = [4, 5, 0, -2, -3, 1]，k = 5：

1. 初始状态：hash[0] = 1，表示从数组开始的和能被 k整除的情况。

2. 遍历数组，逐步计算前缀和 sum及其余数 r = (sum % k + k) % k，然后在 hash中查找相同余数出现次数并累加至结果中。

   • 第一次循环：sum = 4，r = 4
     • hash[4] = 1更新
   • 第二次循环：sum = 9，r = 4
     • hash[4]已存在，累加结果 ret += 1
     • 更新 hash[4] = 2
   • 第三次循环：sum = 9，r = 4
     • hash[4]已存在，累加结果 ret += 2
     • 更新 hash[4] = 3
   • 第四次循环：sum = 7，r = 2
     • hash[2] = 1更新
   • 第五次循环：sum = 4，r = 4
     • hash[4]已存在，累加结果 ret += 3
     • 更新 hash[4] = 4
   • 第六次循环：sum = 5，r = 0
     • hash[0]已存在，累加结果 ret += 1
     • 更新 hash[0] = 2

最终结果 ret = 7，即共有 7 个子数组满足和能被 k整除的条件。

C++代码实现

classSolution{ public:intsubarraysDivByK(vector<int>&nums,intk){ unordered_map<int,int>hash;// 记录前缀和余数出现的次数hash[0]=1;// 确保能统计到从起点到i的子数组和为k的情况intsum =0,ret =0;for(autox :nums){ sum +=x;// 计算当前位置的前缀和intr =(sum %k +k)%k;// 修正后的余数if(hash.count(r))ret +=hash[r];// 统计符合条件的余数出现次数hash[r]++;// 更新当前余数出现次数}returnret;}};

易错点提示

1. 初始化 hash[0] = 1：

   • 为了处理从数组起点到 i的子数组和能被 k整除的情况，例如当 sum[i] % k == 0时，需要提前初始化 hash[0] = 1，否则初始状态无法统计正确的结果。

2. 负数取模的修正：

   • 负数取模在 C++ 中保留负号。例如，-1 % 5 = -1。为了保证余数为非负，我们使用 (sum % k + k) % k表达式，确保余数始终落在 [0, k-1]范围。

3. 返回值累加逻辑：

   • 每次 sum % k在哈希表中找到时，将其对应的次数累加到 ret中，即前缀和为 i的位置符合条件的子数组个数。

代码解读

我们使用前缀和和同余定理，将问题简化为寻找具有相同余数的前缀和数量。在一次遍历中快速统计出满足条件的子数组数量。

• 时间复杂度：O(n)，因为只需遍历数组一次。
• 空间复杂度：O(k)，哈希表存储 k种余数

2.3 连续数组（medium）

题目链接：525. 连续数组

题目描述：

给定一个二进制数组 nums，找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：

• 输入：nums = [0,1]
  输出：2
  说明：[0, 1]是具有相同数量 0 和 1 的最长连续子数组。

示例 2：

• 输入：nums = [0,1,0]
  输出：2
  说明：[0, 1](或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

提示：

• 1 <= nums.length <= 10^5
• nums[i]不是 0 就是 1

解法（前缀和 + 哈希表）

算法思路：

• 将 0 视为 -1，1 视为 1，这样问题转化为寻找连续区间的和为 0。
• 使用前缀和来记录当前位置的和，目标是找到第一个与当前和相等的前缀和的位置，以便计算出最长子数组的长度。

1. 初始化：

   • 使用哈希表记录每种前缀和首次出现的位置。初始化时，将前缀和为 0 的位置设为 -1。

2. 遍历数组：

   • 计算当前的前缀和。如果该前缀和已存在于哈希表中，说明找到了一个和为 0 的区间，更新最长长度。
   • 如果前缀和不存在于哈希表中，则将其加入哈希表，记录首次出现的位置。

示例分析

假设 nums = [0, 1, 0]：

1. 初始状态：hash[0] = -1
2. 遍历 nums：
   • 第 0 次循环：sum = -1（0 转换为 -1），hash[-1] = -1，首次出现，记录 hash[-1] = 0。
   • 第 1 次循环：sum = 0，此时 sum已存在于 hash，计算 ret = 1 - (-1) = 2。
   • 第 2 次循环：sum = -1，再次找到 sum已存在，计算 ret = 2 - 0 = 2。

最终结果为 2，即子数组 [0, 1]或 [1, 0]满足条件。

C++代码实现

classSolution{ public:intfindMaxLength(vector<int>&nums){ unordered_map<int,int>hash;hash[0]=-1;// 处理前缀和为 0 的情况intsum =0,ret =0;for(inti =0;i <nums.size();i++){ sum +=(nums[i]==0)?-1:1;// 将 0 视为 -1，1 视为 1if(hash.count(sum))ret =max(ret,i -hash[sum]);// 更新最大长度elsehash[sum]=i;// 记录首次出现的位置}returnret;}};

易错点提示

1. 哈希表初始化：

   • hash[0] = -1确保能统计从起点到 i的子数组和为 0 的情况。

2. 前缀和更新顺序：

   • 在遍历过程中，计算 sum后先查找 hash[sum]，再更新 hash[sum]。

3. 返回值累加逻辑：

   • 计算长度时，利用哈希表中存储的前缀和位置来得到最长子数组的长度。

代码解读

通过使用哈希表存储前缀和出现的次数，我们可以在一次遍历中快速找到和为 0 的最长子数组的长度。

• 时间复杂度：O(n)，只需遍历数组一次。
• 空间复杂度：O(n)，最坏情况下，可能存储 n 个不同的前缀和。

2.4 矩阵区域和（medium）

题目链接：1314. 矩阵区域和

题目描述：

给你一个 m x n 的矩阵 mat和一个整数 k，请你返回一个矩阵 answer，其中每个 answer[i][j]是所有满足以下条件的元素 mat[r][c]的和：

• i - k <= r <= i + k
• j - k <= c <= j + k
• (r, c)在矩阵内。

示例 1：

• 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
  输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

• 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
  输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

解法（二维前缀和）

算法思路：

• 使用二维前缀和的概念来高效计算每个 (i, j)位置的矩阵区域和。
• 首先构造一个前缀和矩阵 dp，然后根据区域的左上角和右下角的坐标来快速获取所需的和。

1. 初始化前缀和矩阵：

   • 构造一个 (m + 1) x (n + 1)的前缀和矩阵 dp，其中 dp[i][j]表示 mat矩阵中 (0,0)到 (i-1,j-1)的元素和。

2. 计算前缀和：

   • 遍历原矩阵 mat，根据前缀和的性质填充 dp。

3. 计算区域和：

   • 对于每个位置 (i, j)，计算左上角和右下角的坐标，然后利用前缀和矩阵快速得到区域和。

示例分析

假设 mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]，k = 1：

1. 初始化前缀和矩阵 dp：

   • 计算出 dp，其中 dp[i][j]是对应矩阵区域的和。

2. 对于 i=1, j=1位置：

   • 左上角坐标 (0, 0)和右下角坐标 (2, 2)。
   • 通过 dp计算：
     • ret[1][1] = dp[2][2] - dp[0][2] - dp[2][0] + dp[0][0]。

最终得到的矩阵区域和为 [[12, 21, 16], [27, 45, 33], [24, 39, 28]]。

C++代码实现

classSolution{ public:vector<vector<int>>matrixBlockSum(vector<vector<int>>&mat,intk){ intm =mat.size(),n =mat[0].size();vector<vector<int>>dp(m +1,vector<int>(n +1));// 1. 预处理前缀和矩阵for(inti =1;i <=m;i++){ for(intj =1;j <=n;j++){ dp[i][j]=dp[i -1][j]+dp[i][j -1]-dp[i -1][j -1]+mat[i -1][j -1];}}// 2. 计算区域和vector<vector<int>>ret(m,vector<int>(n));for(inti =0;i <m;i++){ for(intj =0;j <n;j++){ intx1 =max(0,i -k),y1 =max(0,j -k);intx2 =min(m -1,i +k),y2 =min(n -1,j +k);ret[i][j]=dp[x2 +1][y2 +1]-dp[x1][y2 +1]-dp[x2 +1][y1]+dp[x1][y1];}}returnret;}};

易错点提示

1. 边界条件：

   • 确保左上角和右下角的坐标在矩阵范围内，通过 max和 min函数处理。

2. 前缀和更新：

   • 在计算前缀和时，要注意从 (1,1)开始填充，以避免越界。

3. 结果计算逻辑：

   • 注意在 dp矩阵中使用的是 x2 + 1和 y2 + 1，因为 dp矩阵是多一行和多一列的。

代码解读

通过构建前缀和矩阵，可以在 O(1) 时间内计算任意区域的和，使得整个算法的时间复杂度为 O(m * n)，而空间复杂度也是 O(m * n)，适合给定的约束条件。

写在最后

前缀和作为一种高效的数据结构，极大地简化了众多数组与矩阵相关问题的求解过程。本文通过解析具体问题，如和为 k 的子数组、和可被 k 整除的子数组及最长连续数组，展示了前缀和与哈希表结合的威力。每个示例不仅提供了解法，还详细解释了代码实现的思路与易错点，帮助读者更好地理解与掌握。通过这些深入的分析，读者能够在面临复杂问题时，更自信地运用前缀和的技巧，提升解题效率。

以上就是关于【优选算法篇】前缀之美，后缀之韵：于数列深处追寻算法的动与静的内容啦，各位大佬有什么问题欢迎在评论区指正，您的支持是我创作的最大动力！❤️