探索算法系列 - 前缀和算法

目录

一维前缀和（原题链接）

二维前缀和（原题链接）

寻找数组的中心下标（原题链接）

除自身以外数组的乘积（原题链接）

和为 K 的子数组（原题链接）

和可被 K 整除的子数组（原题链接）

连续数组（原题链接）

矩阵区域和（原题链接）

---

一维前缀和（原题链接）

描述：

给定一个长度为n的数组a1,a2,....ana1​,a2​,....an​.

接下来有q次查询, 每次查询有两个参数l, r.

对于每个询问, 请输出

输入描述：

第一行包含两个整数n和q.

第二行包含n个整数, 表示a1,a2,....ana1​,a2​,....an​.

接下来q行,每行包含两个整数   l和r.

输出描述：

输出q行,每行代表一次查询的结果.

解题思路：

• 读取输入：读取数组的长度 n 和查询的次数 q，接着读取数组的元素。
• 前缀和计算：
  • 创建一个 dp 数组，其中 dp[i] 存储从数组的起始位置到第 i 个元素的和。
  • 通过前缀和数组 dp，可以快速计算任意子区间 [l, r] 的和。
• 处理查询：
  • 对于每个查询 (l, r)，利用前缀和数组 dp 来计算区间和 dp[r] - dp[l-1]，并输出结果。

步骤说明：

• 输入处理：

  • 使用 cin 读取输入的数组大小 n 和查询次数 q。
  • 读取数组的元素并存储到 arr 中。

• 计算前缀和：

  • 初始化前缀和数组 dp。
  • 使用一个循环来填充 dp 数组，其中 dp[i] 是从数组的开始到第 i 个元素的累积和。

• 查询处理：

  • 读取每个查询的区间 [l, r]。
  • 计算并输出区间 [l, r] 的和，这通过前缀和数组 dp 来实现。

具体代码：

#include <iostream>
#include <vector>using namespace std;int main() 
{int n, q;cin >> n >> q;  // 读取数组的大小 n 和查询的数量 qvector<int> arr(n + 1);  // 创建一个大小为 n + 1 的数组，索引从 1 开始for(int i = 1; i <= n; i++)cin >> arr[i];  // 读取数组元素vector<long long> dp(n + 1);  // 创建前缀和数组 dp，大小为 n + 1for(int i = 1; i <= n; i++)dp[i] = dp[i-1] + arr[i];  // 计算前缀和，dp[i] 是从 arr[1] 到 arr[i] 的累积和int l, r;while(q--)  // 对于每个查询{cin >> l >> r;  // 读取查询的区间 [l, r]// 计算并输出区间 [l, r] 的和cout << dp[r] - dp[l - 1] << endl;  }return 0;
}

二维前缀和（原题链接）

描述：

给你一个 n 行 m 列的矩阵 A ，下标从1开始。
接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，

输入描述：

第一行包含三个整数n,m,q.
接下来n行，每行m个整数，代表矩阵的元素
接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数

输出描述：

输出q行，每行表示查询结果。

解题思路：

• 输入处理：

  • 读取二维数组的行数 n、列数 m 和查询的次数 q。
  • 读取二维数组的数据并存储到 arr 中。

• 前缀和计算：

  • 创建一个二维前缀和数组 dp，用来存储从 (1, 1) 到 (i, j) 的矩阵和。
  • 计算 dp 数组的值，通过动态规划公式进行填充：
    dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j] 这个公式用于去除重复计算的区域，并包含当前元素 arr[i][j]。

• 查询处理：

  • 对于每个查询 (x1, y1, x2, y2)，使用前缀和数组 dp 快速计算子矩阵的和：
    dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 其中，dp[x2][y2] 是从 (1, 1) 到 (x2, y2) 的矩阵和，减去 dp[x1-1][y2] 和 dp[x2][y1-1]，再加上 dp[x1-1][y1-1] 修正重叠区域。

步骤说明：

• 取输入数据：

  • 读取 n、m 和 q。
  • 读取二维数组的元素到 arr 中。

• 计算二维前缀和：

  • 初始化 dp 数组为零。
  • 通过嵌套循环填充 dp 数组，使用动态规划公式来计算前缀和。

• 处理查询并输出结果：

  • 对每个查询 (x1, y1, x2, y2)，利用前缀和数组 dp 计算子矩阵的和，并输出结果。

具体代码：

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n = 0, m = 0, q = 0;cin >> n >> m >> q;  // 读取矩阵的行数 n、列数 m 和查询的数量 q// 创建并填充二维数组 arr，索引从 1 开始vector<vector<int>> arr(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> arr[i][j];  // 读取矩阵元素// 创建并计算二维前缀和数组 dpvector<vector<long long>> dp(n + 1, vector<long long>(m + 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] + arr[i][j];  // 计算前缀和int x1 = 0, y1 = 0, x2 = 0, y2 = 0;while(q--)  // 处理每一个查询{cin >> x1 >> y1 >> x2 >> y2;  // 读取查询的四个角坐标// 计算并输出子矩阵的和cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;}return 0;
}

寻找数组的中心下标（原题链接）

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

解题思路：

• 定义前缀和和后缀和：

  • 使用两个数组 f 和 g，分别存储当前索引 i 左侧和右侧元素的和。
  • f[i] 代表从数组开头到索引 i-1 的和，即索引 i 之前的所有元素的和。
  • g[i] 代表从索引 i+1 到数组末尾的和，即索引 i 之后的所有元素的和。

• 计算前缀和和后缀和：

  • 从左到右计算前缀和 f。
  • 从右到左计算后缀和 g。

• 查找枢轴索引：

  • 遍历数组，如果 f[i] 等于 g[i]，则 i 是一个枢轴索引，返回 i。
  • 如果没有找到合适的索引，返回 -1。

步骤说明：

• 初始化和计算前缀和 f：

  • 遍历数组，从索引 1 开始到数组的最后一个元素，逐步累加前面的元素和。

• 初始化和计算后缀和 g：

  • 从数组的倒数第二个元素开始，逐步累加后面的元素和。

• 查找满足条件的索引：

  • 遍历整个数组，如果某个索引 i 的前缀和 f[i] 等于后缀和 g[i]，返回 i。

• 返回结果：

  • 如果没有找到符合条件的索引，返回 -1。

具体代码：

class Solution 
{
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n, 0), g(n, 0);// 计算前缀和 ffor(int i = 1; i < n; i++)f[i] = f[i - 1] + nums[i - 1];// 计算后缀和 gfor(int i = n - 2; i >= 0; i--)g[i] = g[i + 1] + nums[i + 1];// 查找枢轴索引for(int i = 0; i < n; i++){if(f[i] == g[i])return i;}// 没有找到枢轴索引return -1;}
};

除自身以外数组的乘积（原题链接）

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

解题思路：

• 定义前缀积和后缀积：

  • lprod[i] 表示数组 nums 中从起始位置到索引 i-1 的所有元素的乘积（前缀积）。
  • rprod[i] 表示数组 nums 中从索引 i+1 到末尾的所有元素的乘积（后缀积）。

• 计算前缀积：

  • 从左到右遍历数组，计算每个位置 i 左侧所有元素的乘积并存储在 lprod[i] 中。

• 计算后缀积：

  • 从右到左遍历数组，计算每个位置 i 右侧所有元素的乘积并存储在 rprod[i] 中。

• 计算结果数组：

  • 对于每个位置 i，结果数组 ret[i] 是 lprod[i] 和 rprod[i] 的乘积，表示去掉 nums[i] 后的所有元素的乘积。

步骤说明：

• 初始化：

  • lprod 和 rprod 数组的大小都为 n + 1。
  • lprod[0] 初始化为 1，因为没有元素在位置 0 的左边。
  • rprod[n-1] 初始化为 1，因为没有元素在位置 n-1 的右边。

• 计算前缀积：

  • 遍历数组，从位置 1 开始，逐步计算前缀积并填充 lprod。

• 计算后缀积：

  • 遍历数组，从位置 n-2 开始，逐步计算后缀积并填充 rprod。

• 生成结果数组：

  • 遍历数组，将每个位置的 ret[i] 计算为 lprod[i] * rprod[i]。

具体代码：

class Solution 
{
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();// lprod 表示 [0, i - 1] 区间内所有元素的乘积// rprod 表示 [i + 1, n - 1] 区间内所有元素的乘积vector<int> lprod(n, 1), rprod(n, 1);  // 不需要 n + 1 的大小// 计算前缀积for (int i = 1; i < n; i++)lprod[i] = lprod[i - 1] * nums[i - 1];// 计算后缀积for (int i = n - 2; i >= 0; i--)rprod[i] = rprod[i + 1] * nums[i + 1];// 生成结果数组vector<int> ret(n);for (int i = 0; i < n; i++)ret[i] = lprod[i] * rprod[i];return ret;}
};

和为 K 的子数组（原题链接）

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

子数组是数组中元素的连续非空序列。

解题思路：

• 前缀和：

  • 使用前缀和来表示从数组开始到当前位置的和。
  • 对于每个位置 i，计算到当前位置的前缀和 sum。

• 哈希表记录前缀和的出现次数：

  • 使用一个哈希表 hash 来记录前缀和及其出现的次数。hash[sum] 代表前缀和 sum 出现的次数。

• 查找目标和：

  • 对于当前位置的前缀和 sum，检查 sum - k 是否在哈希表中存在。
  • 如果存在，则表示存在子数组和为 k，将 hash[sum - k] 加到结果 ret 中，hash[sum - k] 表示到当前位置的子数组个数。

• 更新哈希表：

  • 每次更新当前前缀和 sum 在哈希表中的计数。

步骤说明：

• 初始化：

  • 创建一个哈希表 hash，并将 hash[0] 初始化为 1。这个设置是为了处理前缀和等于 k 的情况。

• 计算前缀和并查找目标和：

  • 遍历数组，累加前缀和 sum。
  • 如果 sum - k 在哈希表中存在，则结果 ret 增加 hash[sum - k]，表示找到的符合条件的子数组的个数。

• 更新哈希表：

  • 将当前前缀和 sum 的计数增加。

具体代码：

class Solution 
{
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> hash; // 统计前缀和出现的次数hash[0] = 1; // 处理前缀和等于 k 的情况int sum = 0, ret = 0;for (auto x : nums) {sum += x; // 计算当前位置的前缀和// 检查 sum - k 是否在哈希表中if (hash.count(sum - k))ret += hash[sum - k]; // 如果存在，累加结果// 更新哈希表hash[sum]++;}return ret;}
};

和可被 K 整除的子数组（原题链接）

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

子数组 是数组中 连续 的部分。

 解题思路：

• 前缀和：

  • 计算从数组起始到当前位置的前缀和 sum。
  • 对于每个位置 i，前缀和 sum 是从数组开始到位置 i 的所有元素之和。

• 余数计算：

  • 对于每个前缀和 sum，计算它模 k 的余数 r。
  • 由于余数可能是负数，因此需要进行调整，使余数始终是非负的。计算公式为 (sum % k + k) % k。

• 哈希表记录余数出现次数：

  • 使用一个哈希表 hash 来记录每个余数出现的次数。
  • 如果当前余数 r 已经在哈希表中出现过，那么存在以之前某个位置为结束的子数组和能被 k 整除。累加 hash[r] 到结果 ret。

• 更新哈希表：

  • 每次更新当前余数 r 的计数。

步骤说明：

• 初始化哈希表：

  • hash[0 % k] = 1：这个设置是为了处理从数组开头到当前位置的和能被 k 整除的子数组。初始值为 1 表示前缀和为 0（即不包括任何元素）的情况。

• 计算前缀和和余数：

  • 遍历数组，对每个元素 x 更新前缀和 sum。
  • 计算当前前缀和 sum 的模 k 的余数 r，并调整为非负值。

• 查找和更新哈希表：

  • 如果余数 r 存在于哈希表中，将其出现次数 hash[r] 加到结果 ret。
  • 更新哈希表中余数 r 的计数。

具体代码：

class Solution 
{
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash;hash[0 % k] = 1; // 初始余数 0 的出现次数为 1int sum = 0, ret = 0;for (auto x : nums) {sum += x;                  // 计算当前位置的前缀和int r = (sum % k + k) % k; // 修正后的余数// 如果该余数曾出现过，则累加结果if (hash.count(r))ret += hash[r];// 更新当前余数的计数hash[r]++;}return ret;}
};

连续数组（原题链接）

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

解题思路：

• 前缀和的概念：

  • 计算当前前缀和，将数组中的 0 视为 -1，将 1 视为 +1。这样，如果一个子数组中的 0 和 1 的数量相等，那么该子数组的前缀和在开始和结束的位置是相同的。

• 使用哈希表记录前缀和的第一次出现位置：

  • 使用哈希表 hash 来记录每个前缀和首次出现的位置。
  • 如果前缀和已经出现过，则表示从之前出现位置到当前的位置形成的子数组是 0 和 1 数量相等的子数组。计算这个子数组的长度，并更新最大长度 ret。

• 处理前缀和为 0 的特殊情况：

  • 初始化哈希表时，将 hash[0] 设置为 -1。这是为了处理从数组开头到当前索引的子数组，前缀和为 0 的情况。

步骤说明：

• 初始化哈希表：

  • hash[0] = -1：这个设置表示前缀和为 0 的情况发生在虚拟的数组起点之前的位置 -1。

• 计算前缀和并查找：

  • 遍历数组，对每个元素 nums[i]，将其转化为 1（如果是 1）或者 -1（如果是 0），并累加到 sum 中。
  • 使用哈希表检查当前前缀和 sum 是否已出现过。如果出现过，计算当前子数组的长度，并更新最大长度 ret。
  • 如果当前前缀和 sum 未出现过，将其位置 i 存储到哈希表中。

具体代码：

class Solution 
{
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash;hash[0] = -1; // 默认前缀和为 0 的情况int sum = 0, ret = 0;for (int i = 0; i < nums.size(); i++) {// 将 0 转换为 -1，1 保持不变，计算前缀和sum += nums[i] == 0 ? -1 : 1;// 如果当前前缀和 sum 已出现，计算当前子数组长度if (hash.count(sum))ret = max(ret, i - hash[sum]);else// 记录当前前缀和的第一次出现位置hash[sum] = i;}return ret;}
};

矩阵区域和（原题链接）

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

 解题思路：

• 前缀和矩阵：

  • 构建一个前缀和矩阵 dp，使得 dp[i][j] 表示从矩阵的左上角到位置 (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]。

• 计算每个位置的 k x k 子矩阵的和：

  • 对于每个位置 (i, j)，计算以该位置为中心的 k x k 子矩阵的和。
  • 确定子矩阵的边界：上边界 x1、左边界 y1、下边界 x2 和右边界 y2。
  • 使用前缀和矩阵 dp 来计算子矩阵的和： sum=dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]+dp[x1−1][y1−1]\text{sum} = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]sum=dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]+dp[x1−1][y1−1]
  • 处理边界条件以确保索引不越界。

步骤说明：

• 构建前缀和矩阵：

  • 遍历矩阵 mat，使用前缀和的公式计算 dp 矩阵。

• 计算每个位置的 k x k 子矩阵的和：

  • 对于每个位置 (i, j)，计算子矩阵的边界并通过前缀和矩阵 dp 计算和。

具体代码：

class Solution 
{
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));// 1. 预处理前缀和矩阵for (int i = 1; i <= m; i++)for (int j = 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. 使用前缀和矩阵计算每个位置的 k x k 子矩阵的和vector<vector<int>> ret(m, vector<int>(n));for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;int x2 = min(m - 1, i + k) + 1, y2 = min(n - 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;}
};