暴雪战网官方网站入口,霸气又聚财的公司名字大全,网站建设费计入那个科目,孝感网站制作公司文章目录 前言一、一维前缀和模板二、二维前缀和模板三、寻找数组的中心下标四、除自身以外数组的乘积五、和为 K 的子数组六、和可被 K 整除的子数组七、连续数组八、矩阵区域和 前言
本章将深度剖析前缀和#xff0c;以及总结前缀和模板。
前缀和是一种在算法和数据处理中… 文章目录 前言一、一维前缀和模板二、二维前缀和模板三、寻找数组的中心下标四、除自身以外数组的乘积五、和为 K 的子数组六、和可被 K 整除的子数组七、连续数组八、矩阵区域和 前言
本章将深度剖析前缀和以及总结前缀和模板。
前缀和是一种在算法和数据处理中的重要技巧特别适合解决连续子数组求和的问题。通过构建一个前缀和数组我们可以快速查询任意连续区间的和从而在一定程度上优化时间复杂度。
基本原理 前缀和的核心思想是预先计算数组的前缀和使得区间求和可以在常数时间内完成。假设有一个数组 ( arr )其前缀和数组定义如下
设 ( prefix[i] ) 表示从数组起点到位置 ( i ) 的元素之和。因此前缀和数组 ( prefix ) 可以定义为 [ prefix[i] arr[0] arr[1] \dots arr[i] ]
计算任意区间和 ( arr[l] arr[l1] \dots arr[r] ) 可以通过前缀和快速得到 [ arr[l] arr[l1] \dots arr[r] prefix[r] - prefix[l-1] ] 其中 ( prefix[r] ) 是从 ( arr[0] ) 到 ( arr[r] ) 的和减去从 ( arr[0] ) 到 ( arr[l-1] ) 的和就得到了区间 ( [l, r] ) 的和。
例子 假设有数组 ( arr [1, 2, 3, 4, 5] )构建前缀和数组 ( prefix ) 如下
( prefix[0] 1 )( prefix[1] 1 2 3 )( prefix[2] 1 2 3 6 )( prefix[3] 1 2 3 4 10 )( prefix[4] 1 2 3 4 5 15 )
那么求区间和 ( arr[1] arr[2] arr[3] ) 就可以通过前缀和数组计算 [ arr[1] arr[2] arr[3] prefix[3] - prefix[0] 10 - 1 9 ]
时间复杂度
构建前缀和数组的时间复杂度为 ( O(n) )其中 ( n ) 是数组的长度。一旦构建好前缀和数组查询任意区间的和的时间复杂度为 ( O(1) )。
前缀和技术通常用于快速解决子数组求和、二维区域求和等问题。 一、一维前缀和模板
【模板】前缀和
#include iostream
using namespace std;
#includevector
typedef long long LL;int n,q;int main()
{cin n q;vectorLL arr(n 1);for (int i 1; i n; i){cin arr[i];}//定义前缀和数组vectorLL dp(n 1);for (int i 1; i n; i){dp[i] dp[i - 1] arr[i];}//使用前缀和数组while (q--){LL l, r;cin l r;cout dp[r] - dp[l - 1] endl;}return 0;
}二、二维前缀和模板
【模板】二维前缀和 #include iostream
using namespace std;#includevector
typedef long long LL;int main()
{int n, m, q;cin n m q;//初始化原始数据vectorvectorLL arr(n 1, vectorLL (m 1));for (int i 1; i n; i){for (int j 1; j m; j){cin arr[i][j];}}//定义前缀和数组vectorvectorLL dp(n 1, vectorLL (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] arr[i][j] - dp[i - 1][j - 1];}}//使用前缀和数组while (q--){LL x1, y1, x2, y2;cin x1 y1 x2 y2;cout dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] dp[x1 - 1][y1 - 1] endl;}return 0;
}三、寻找数组的中心下标
寻找数组的中心下标 算法思路
根据中心下标的定义除中心下标元素外该元素左边的「前缀和」应等于右边的「后缀和」。
因此可以先预处理两个数组一个表示前缀和另一个表示后缀和。然后用一个 for 循环枚举可能的中心下标判断每个位置的前缀和和后缀和是否相等如果相等则返回该下标。
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();//构建前缀和vectorint dp_first(n);dp_first[0] 0;for (int i 1; i n; i){dp_first[i] dp_first[i - 1] nums[i - 1];}//构建后缀和vectorint dp_end(n);dp_end[n - 1] 0;for (int i n - 2; i 0; i--){dp_end[i] dp_end[i 1] nums[i 1];}//使用前缀和for (int i 0; i n; i){if (dp_first[i] dp_end[i])return i;}return -1;}
};四、除自身以外数组的乘积
除自身以外数组的乘积 算法思路
题目要求不能使用除法并要求在 O ( N ) O(N) O(N) 时间复杂度内完成排除了暴力解法和计算数组乘积后除以单个元素的方法。
分析可知每个位置的最终结果 ret[i] 可以分为两部分
前缀积部分nums[0] * nums[1] * ... * nums[i - 1]后缀积部分nums[i 1] * nums[i 2] * ... * nums[n - 1]
可以利用前缀和的思想定义两个数组 post 和 suf分别存储两部分信息
post表示 i 位置之前所有元素的前缀乘积即 [0, i - 1] 区间的乘积。suf表示 i 位置之后所有元素的后缀乘积即 [i 1, n - 1] 区间的乘积。
最后根据 post 和 suf 计算出每个位置的最终结果。
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();//构建前缀积vectorint dp_first(n);dp_first[0] 1;for (int i 1; i n; i){dp_first[i] dp_first[i - 1] * nums[i - 1];}//构建后缀积vectorint dp_end(n);dp_end[n - 1] 1;for (int i n - 2; i 0; i--){dp_end[i] dp_end[i 1] * nums[i 1];}//使用前后缀积vectorint answer(n);for (int i 0; i n; i){answer[i] dp_first[i] * dp_end[i];}return answer;}
};五、和为 K 的子数组
和为 K 的子数组 将前缀和存入哈希表
算法思路
设 i 为数组中的任意位置sum[i] 表示 [0, i] 区间内所有元素的和。
我们需要找到“以 i 为结尾且和为 k 的子数组”这等价于找出所有可能的起始位置 x1, x2, x3...使得 [x, i] 区间的和为 k。此时[0, x] 区间的和应为 sum[i] - k。
因此问题转化为
找出 [0, i - 1] 区间内有多少前缀和等于 sum[i] - k。
无需真正初始化前缀和数组因为我们只关注 i 位置之前前缀和为 sum[i] - k 的次数。我们可以使用一个哈希表在计算当前位置的前缀和时同时记录每个前缀和出现的次数。 class Solution {
public:int subarraySum(vectorint nums, int k) {// 哈希表模拟前缀和数组unordered_mapint, int hash;hash[0] 1;//使用前缀和数组int sum 0, ret 0;for (auto e : nums){sum e;if (hash.count(sum - k)) ret hash[sum - k];hash[sum];}return ret;}
}; 六、和可被 K 整除的子数组
和可被 K 整除的子数组 本题需要的前置知识 同余定理 若 (a - b) % n 0则 a % n b % n。也就是说如果两个数之差能被 n 整除那么这两个数对 n 取模的结果相同。 例如(26 - 2) % 12 0所以 26 % 12 2 % 12 2。 C 中负数取模结果的处理 在 C 中负数取模的结果会保留负号例如 -1 % 3 -1。为防止负数结果影响常用 (a % n n) % n 确保结果为正例如-1 % 3 (-1 % 3 3) % 3 2。
算法思路
此题与 LeetCode 560 题“和为 K 的子数组”思路类似。
设 i 为数组中的任意位置sum[i] 表示 [0, i] 区间内的和。
要找出“以 i 为结尾、和可被 k 整除的子数组”需要找到所有起点 x1, x2, x3... 使得 [x, i] 的和能被 k 整除。假设 [0, x - 1] 的和为 a[0, i] 的和为 b则有 (b - a) % k 0。根据同余定理[0, x - 1] 区间和 [0, i] 区间的前缀和同余。因此问题变成 找到 [0, i - 1] 中前缀和的余数等于 sum[i] % k 的个数。
无需初始化前缀和数组只需用一个哈希表记录每种前缀和的出现次数同时计算当前位置的前缀和。
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {// 哈希表模拟前缀和数组unordered_mapint,int hash;hash[0] 1;//使用前缀和数组int sum 0, ret 0;for (auto e : nums){sum e;int r (sum % k k) % k;if (hash.count(r)) ret hash[r];hash[r];}return ret;}
};七、连续数组
连续数组 算法思路
稍作转换这道题可以化为经典问题
本题需要找一个连续区间使得 0 和 1 出现的次数相同。将 0 视为 -11 视为 1问题就转化为找一个区间使其和等于 0。
这样问题与 LeetCode 560 题“和为 K 的子数组”思路相似。
设 i 为数组中任意位置用 sum[i] 表示 [0, i] 区间内所有元素的和。我们希望找到最大长度的“以 i 为结尾、和为 0 的子数组”这需要找到从左至右第一个位置 x1 使得 [x1, i] 的和为 0。此时 [0, x1 - 1] 区间的和等于 sum[i]。因此问题变成
找到 [0, i - 1] 区间内首次出现 sum[i] 的位置即可。
我们无需真正初始化一个前缀和数组因为只关心 i 位置之前首次出现等于 sum[i] 的前缀和位置。只需一个哈希表在计算当前位置前缀和的同时记录该前缀和的首次出现位置。
class Solution {
public:int findMaxLength(vectorint nums) {// 哈希表模拟前缀和数组unordered_mapint, int hash;hash[0] -1; // 使用前缀和数组int sum 0, ret 0;for (int i 0; i nums.size(); i){sum nums[i] 0 ? -1 : 1;if (hash.count(sum)) ret max(ret, i - hash[sum]);else hash[sum] i;} return ret;}
};八、矩阵区域和
矩阵区域和
算法思路
这道题主要是二维前缀和的基本应用关键在于填写结果矩阵时找到原矩阵对应区域的「左上角」和「右下角」坐标建议画图理解。
左上角坐标x1 i - ky1 j - k为了不超出矩阵范围需要对 0 取 max修正后的坐标为x1 max(0, i - k)y1 max(0, j - k)。右下角坐标x2 i ky2 j k同理为避免超出矩阵范围需要对 m - 1 和 n - 1 取 min修正后的坐标为x2 min(m - 1, i k)y2 min(n - 1, j k)。
最后将修正后的坐标代入二维前缀和的计算公式即可注意下标的映射关系。
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {// 构建二维前缀和int n mat.size(), m mat[0].size();vectorvectorint dp(n 1, vectorint (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] mat[i - 1][j - 1] - dp[i - 1][j - 1];}} //使用二维前缀和vectorvectorint answer(n, vectorint (m));for (int i 0; i n; i){for (int j 0; j m; j){int a, b, c, d;a i - k 0 ? 1 : i - k 1;b j - k 0 ? 1 : j - k 1;c i k n ? n : i k 1;d j k m ? m : j k 1;answer[i][j] dp[c][d] - dp[c][b - 1] - dp[a - 1][d] dp[a - 1][b - 1];}}return answer;}
};
