【算法一周目】从时光的边缘看世界：前缀和揭示的算法真谛

文章目录

• 1.一维前缀和
• 2.二维前缀和
• 3.寻找数组的中心下标
• 4.除自身以外数组的乘积
• 5.和为k的子数组
• 6.和可被k整除的子数组
• 7.连续数组
• 8.矩阵区域和

1.一维前缀和

题目链接： 【模板】一维前缀和

题目描述：

给定一个长度为 n 的整数数组 arr 和 q 个查询，每个查询由两个整数 l 和 r 组成，表示区间 [l, r]。请计算出每个区间内所有元素的和。

示例 1：

• 输入：arr = [1, 2, 3, 4, 5], q = 2, 查询区间为 [(1, 3), (2, 4)]
• 输出：[6, 9]
• 解释：区间 [1, 3] 的元素和为 1 + 2 + 3 = 6，区间 [2, 4] 的元素和为 2 + 3 + 4 = 9。

提示：

• 1 <= n, q <= 100000
• -10000 <= arr[i] <= 10000

---

解题思路
对于本道题，我们可以提前预处理出一个前缀和数组 $dp$ ，通过前缀和数组快速求出某个区间所有元素的和。

前缀和数组 $dp[i]$ 表示数组起始位置到第 $i$ 个位置的所有元素和。其递推公式我们很容易得出：

• $dp[i]=dp[i-1]+arr[i]$

计算区间 $[l,r]$ 的所有元素的和：

• $sum=dp[r]-dp[l-1]$

代码实现

#include #include using namespace std;int main() { //处理输入输出 int n, q; cin >> n >> q; vector<int> arr(n + 1); for(int i = 1; i <= n; ++i) cin >> arr[i]; //预处理dp数组，long long元素类型防止溢出 vector<long long> dp(n + 1); for(int i = 1; i <= n; ++i) dp[i] = dp[i - 1] + arr[i]; int l, r; while(q--) { cin >> l >> r; cout << dp[r] - dp[l - 1] << endl; } return 0;}

细节处理：我们开辟前缀和数组时开的空间大小应该比数组的大1（开辟 $n+1$ 的空间），可以让数组的元素位置与下标一一对应（第一个元素对应下标1位置），帮助我们规避掉像 $dp[1]$ 等边界情况。

---

2.二维前缀和

题目链接：【模板】二维前缀和

题目描述：

给定一个大小为 n × m 的矩阵 matrix 和 q 个查询，每个查询由四个整数 x1, y1, x2, y2 组成，表示一个子矩阵的左上角 (x1, y1) 和右下角 (x2, y2)。请计算出每个子矩阵内所有元素的和。

示例 1：

• 输入：matrix = [[1, 2], [3, 4]], q = 1, 查询区间为 [(1, 1, 2, 2)]
• 输出：[10]
• 解释：子矩阵包含所有元素 1 + 2 + 3 + 4 = 10。

提示：

• 1 <= n, m <= 1000
• -10000 <= matrix[i][j] <= 10000

---

解题思路

这道题与上一道题类似，我们可以提前预处理出一个前缀矩阵和数组 $dp$ ，$dp[i][j]$ 表示矩阵从 $[1,1]$ 位置到 $[i,j]$位置的所有元素和，然后利用 $dp$ 数组快速求出子矩阵内所有元素的和。

1. 构建前缀和矩阵数组

   • 构建数组时与上题类似，每一行每一列多开一个空间以此来避免边界情况。
     
   • 递推公式：$dp[i][j]=matrix[i][j]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]$

2. 计算 $[x1.y1]->[x2,y2]$ 任意子矩阵的和 $sum$
   

   • $sum=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]$

代码实现

#include #include using namespace std;int main() { //处理输入数据 int n = 0, m = 0, q = 0; cin >> n >> m >> q; vector<vector<int>> vv(n + 1, vector<int>(m + 1)); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) cin >> vv[i][j]; } //预处理矩阵数组, longlong防溢出  vector<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] + vv[i][j] - dp[i - 1][j - 1]; } //输出 int x1, y1, x2, y2; while(q--) { cin >> x1 >> y1 >> x2 >> y2; long long ret = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]; cout << ret << endl; } return 0;}

---

3.寻找数组的中心下标

题目链接：724. 寻找数组的中⼼下标

题目描述：

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

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

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

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

示例 1：

• 输入：nums = [1, 7, 3, 6, 5, 6]
• 输出：3
• 解释：
  • 中心下标是 3。
  • 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
  • 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，⼆者相等。

示例 2：

• 输入：nums = [1, 2, 3]
• 输出：-1
• 解释：
  • 数组中不存在满足此条件的中心下标。

示例 3：

• 输入：nums = [2, 1, -1]
• 输出：0
• 解释：
  • 中心下标是 0。
  • 左侧数之和 sum = 0，（下标 0 左侧不存在元素），
  • 右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0。

提示：

• 1 <= nums.length <= 10⁴
• -1000 <= nums[i] <= 1000

---

解题思路
根据题目要求，我们可以预处理出一个前缀和数组 $f$ 和后缀和数组 $g$，然后遍历数组通过比较前缀和和后缀和找到中心下标。

1. 前缀和数组

   • $f[i]$ 表示数组开始位置到 $i-1$ 位置的所有元素和
   • 递推公式：$f[i]=f[i-1]+nums[i-1]$

2. 后缀和数组

   • $g[i]$ 表示数组 $i+1$ 位置到数组末尾位置的所有元素和
   • 递推公式：$g[i]=g[i+1]+nums[i+1]$

代码实现

class Solution {public: int pivotIndex(vector<int>& nums) { //预处理出前缀和、后缀和数组 int n = nums.size(); vector<int> f(n); //数组起始位置的左侧 for(int i = 1; i < n; ++i) f[i] = f[i - 1] + nums[i - 1]; vector<int> g(n); for(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$ 的所有元素之和为 $S$ ，中心下标为 $i$ ，$i$ 左边的元素和为 $lsum$ ，根据左侧元素和与右侧元素和相等有：

• $lsum=S-nums[i]-lsum$

稍微化简有：

• $2\times lsum=S-nums[i]$

所以我们只需用一个量 $leftsum$ 记录当前元素的左侧元素和，根据推导公式判断当前位置是否为中心下标。

优化后的解法时间复杂度从 $O(n)$ 降到了 $O(1)$ 了。

class Solution {public: int pivotIndex(vector<int>& nums) { int sum = 0; for(auto e : nums) sum += e; int leftSum = 0; for(int i = 0; i < nums.size(); ++i) { if(2 * leftSum == sum - nums[i]) return i; leftSum += nums[i]; } return -1; }};

---

4.除自身以外数组的乘积

题目链接：238. 除自身以外数组的乘积

题目描述：

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

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

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

示例 1：

• 输入：nums = [1, 2, 3, 4]
• 输出：[24, 12, 8, 6]

示例 2：

• 输入：nums = [-1, 1, 0, -3, 3]
• 输出：[0, 0, 9, 0, 0]

提示：

• 2 <= nums.length <= 10⁵
• -30 <= nums[i] <= 30
• 保证数组 nums 中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

---

解题思路

与上一题类似，我么先预处理出前缀积数组 $f$ 和后缀积数组 $g$ ，然后将两者相乘得到除自身元素以外的乘积。

1. 前缀积数组

• $f[i]$ 表示数组起始位置到第 $i-1$ 位置所有元素的积。
• 递推公式：$f[i]=f[i-1]\times nums[i-1]$

2. 后缀积数组

• $g[i]$ 表示数组第 $i+1$ 位置到数组末尾位置所有元素的积。
• 递推公式：$g[i]=g[i+1]\times nums[i+1]$

细节：$f[0]=g[n-1]=1$，对于这两个数组初始情况需要为1

构建出前缀积与后缀积数组后，我们直接遍历，两者相乘，构建出需要返回的数组 $ret$

代码实现

class Solution {public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> f(n,1); for(int i = 1; i < n; ++i) f[i] = f[i - 1] * nums[i - 1]; vector<int> g(n,1); for(int i = n - 2; i >= 0; --i) g[i] = g[i + 1] * nums[i + 1]; vector<int> ret; for(int i = 0; i < n; ++i) ret.push_back(f[i] * g[i]); return ret; }};

优化解法

我们可以先处理出后缀积 $g$ ，用 pre 记录前缀积（初始化为1），然后遍历将 $pre$ 乘到 $g[i]$ 中，同时维护 $pre$ ，最后将 g 返回即可。

这种写法相较于上种可以少遍历一次数组，而且题目说到输出数组不被视为额外空间，故时间复杂度为 $O(1)$ 。

class Solution {public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> g(n,1); //后缀积 for(int i = n - 2; i >= 0; --i) g[i] = g[i + 1] * nums[i + 1]; //遍历修改g[i] //pre为i位置左侧元素的乘积 int pre = 1; for(int i = 0; i < n; ++i) { g[i] *= pre; pre *= nums[i]; } return g; }};

---

5.和为k的子数组

题目链接：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⁴
• -1000 <= nums[i] <= 1000
• -10⁷ <= k <= 10⁷

---

解题思路

根据题目要求，我们需要求出和为 $K$ 的子数组的个数。

我们可以使用暴力解法，定义两个指针 $i$ 和 $j$ ，固定 $i$ ，$j$ 依次往后遍历，注意，找到符合的数组后，$j$ 也要继续遍历，因为以 $i$ 为起点的和为 $K$ 的子数组不止一个，$j$ 遍历完一遍数组后 $i$ 往后加一，直到 $i$ 遍历完数组，这样就求出和为 $K$ 的子数组的个数，但是暴力解法的时间复杂度是 O( n 2 ) O(n^2) O(n2) ，一定会超时。

对于这道题，我们不能使用滑动窗口，当窗口内出现符合的子数组时，统计个数后窗口的左边端点会前移，因为数组的元素有正有负不满足单调性，这样是会错过一些符合的数组，比如在 $[1,-1,0,0,0]$ 求和为 $0$ 的子数组的个数。

我们的最优解法是前缀和+哈希表。对于 $[0,i]$ 区间的数组，其元素之和为 $sum$ ，如果通过哈希表查询到该区间数组和为 $sum-K$ 的子数组的个数，这样就间接知道了 $[0,i]$ 区间的数组内和为 K 的子数组的个数。

代码实现

class Solution {public: int subarraySum(vector<int>& nums, int k) { //哈希表记录前缀和及其出现的次数 unordered_map<int, int> hash; //处理区间和为K的特殊情况 hash[0] = 1; int sum = 0, ret = 0; for(int i = 0; i < nums.size(); ++i) { //计算[0,i]的前缀和 sum += nums[i]; //查找和为sum-k的子数组的个数 if(hash.count(sum - k)) ret += hash[sum-k]; //将前缀和加入哈希表 hash[sum]++; } return ret; }};

细节处理：

1. 对于前缀和，我们没有必要格外开辟空间来计算，只需要用一个变量 $sum$ 去维护即可。
2. $hash[0]=1$ ：和为 0 的子数组出现的次数默认有一次，这是因为区间元素和刚好第一次为 $K$ 时，按照我们的算法，需要查找和为 $0$ 的子数组个数，但是由于整个区间的所有元素和为 $K$ ，没有额外剩余的元素去构成和为 $0$ 的子数组，所以如果没有 $hash[0]=1$ ，哈希表是查找不到和为 $0$ 的子数组的个数，我们的算法是会遗漏整个区间的和第一次为 $K$ 的情况，最后统计出来的和为 $K$ 的子数组的个数是会少一个的。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$ ，哈希表的空间开销

---

6.和可被k整除的子数组

题目链接：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⁴
• -10⁴ <= nums[i] <= 10⁴
• 2 <= k <= 10^4

---

解题思路

对于这道题，我们依然使用前缀和+哈希表，但是在此之前先引入下同余定理。

同余定理：

• 如果 $(a-b)\mathrm{mod}K==0$ ，则有 $a\mathrm{mod}K==b\mathrm{mod}K$ 。

所以整体思路就是对于 $[0,i]$ 区间的数组，其元素之和为 $sum$ ，对 $sum$ 进行取模($\mathrm{mod}K$)余数为 $mod$ ，如果通过哈希表查询到该区间内数组和的余数同样为 $mod$ 的子数组的个数，这样就间接知道了 $[0,i]$ 区间的数组内和可为 K 整除的子数组的个数。

代码实现

class Solution {public: int subarraysDivByK(vector<int>& nums, int k) { //哈希表存储前缀和余数及其出现的次数 unordered_map<int, int> hash; //处理区间元素和刚好被K整除，余数为0的特殊情况 hash[0] = 1; int ret = 0, sum = 0; for(auto e : nums) { //计算前缀和 sum += e; //对前缀和取模，注意在C++中，余数可为负 //需要换算成非负以免影响结果 int mod = (sum % k + k) % k; //查找前缀和的余数为mod的子数组的个数 if(hash.count(mod)) ret += hash[mod]; //将余数加入哈希表 hash[mod]++; } return ret; }};

代码解析：

1. 哈希表存储的是前缀和的余数及其出现的次数，与上道题不同。

2. $hash[0]=1$ ：余数为 $0$ 默认出现次数为 $1$ 次，是为了处理区间元素和第一次刚好被 $K$ 整除的特殊情况，防止答案遗漏。

3. (sum % k + k) % k ：在C++中，余数可以为负数，需要将其调整为正数，不然会影响结果。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(K)$ ，哈希表存储余数的额外空间开销。

---

7.连续数组

题目链接：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⁵
• nums[i] 不是 0 就是 1

---

解题思路

题目要求我们找含有相同数量的 $0$ 和 $1$ 的最长连续子数组的长度，我们可以将0看作成-1，这样问题就转换成了求和为0的子数组最长长度。

解决这道题的思路依然是前缀和+哈希，对于 $[0,i]$ 区间的数组，其元素之和为 $sum$ ，通过哈希表查询到该区间内数组和同样为 $sum$ 的子数组的末尾元素下标，间接求出和为 $0$ 的子数组长度。

但是需要注意的是，当哈希表中已经存在 $sum$ 时，不必更新 $sum$ 在哈表中的下标，因为题目要求的是子数组最长长度。

代码实现

class Solution {public: int findMaxLength(vector<int>& nums) { //哈希表存储的是[0,i]区间元素和及其下标i unordered_map<int, int> hash; //处理前缀和刚好为0的情况 hash[0] = -1; int sum = 0, ret = 0; for(int i = 0; i < nums.size(); ++i) { //将数组中的0看待成-1 sum += nums[i] == 0 ? -1 : 1; //如果前缀和存在则更新结果，不存在再加入哈希表 if(hash.count(sum)) ret = max(ret, i - hash[sum]); else hash[sum] = i; } return ret; }};

代码解析：

1. 哈希表存储 $[0,i]$ 区间元素和及其下标 $i$ 。
2. $hash[0]=-1$ ：前缀和为 $0$ 的子数组下标默认为 $-14$ ， 处理处理前缀和第一次为 $0$ 的特殊情况。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$ ，哈希表的额外空间开销。

---

8.矩阵区域和

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

题目描述：

给你一个 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-k,j-k]$ 到 $[i+k,j+k]$ 的所有元素的和，我们可以先预处理出来一个矩阵前缀和数组 $dp$ ，然后通过矩阵前缀和数组快速求出子矩阵的所有元素和。

1. 构建矩阵前缀和 $dp$

   • 开辟空间时多开一行和一列，简化边界情况的处理
   • $dp[i][j]$ 表示矩阵 $mat$ 从 $[0,0]$ 到 $[i-1,j-1]$ 的所有元素和。

2. 通过 $dp$ 快速求子矩阵的和

   • 由于矩阵前缀和的下标与矩阵 $mat$ 并不是一一对应的，我们在计算子矩阵的起始位置与末尾位置的下标时要进行转换。

   • 根据题目可知，我们通过 $i$ 和 $j$ 求子矩阵的坐标时是可能会越界，我们要特殊处理。

   • $sum=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]$

代码实现

class Solution {public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { //1.初始化前缀和数组，需要多加一行多加一列 int m = mat.size(), n = mat[0].size(); //dp[i][j]代表矩阵mat从[0][0]到[i-1][j-1]的所有元素的和 vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for(int i = 1; i < m + 1; ++i) for(int j = 1; j < n + 1; ++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(int i = 0; i < m; ++i) { //下标转换并且要进行越界情况的处理 int x1 = max(0, i - k) + 1; int x2 = min(m - 1, i + k) + 1; for(int j = 0; j < n; ++j) { int y1 = max(0, j - k) + 1; int 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; }};

代码解析：

1. 矩阵前缀和 $dp$ 与矩阵 $mat$ 的下标不是一一对应的，比如 $dp[1][1]$ 对应原数组 $mat[0][0]$ ，计算矩阵前缀和要留意。
2. 通过 $i$ 与 $j$ 求子矩阵的坐标时要防止越界并且转换成与 $dp$ 数组对应，因为要通过 $dp$ 求出子矩阵的所有元素和。

• 时间复杂度：$O(m\times n)$
• 空间复杂度：$O(m\times n)$ ，矩阵前缀和数组 $dp$ 的额外空间开销

---

Have a good day😏

See you next time, guys!😁✨🎞