企业官网建设流程全解析

目录

1.前缀和

2.二维前缀和

3.寻找数组的中心下标

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

5.和为K的子数组

6.和可被K惩处的子数组

7.连续数组

1.前缀和

【模板】前缀和_牛客题霸_牛客网

这道题看着题目内容很多，其实就是给出一个指定数组，然后每次查询这个数组的某一段区间之和是多少

这道题就是前缀和算法的基础，毕竟题目都直接写明了前缀和嘛

那么我们就可以根据原数组，创建出一个前缀和数组，对于第i个位置，存储从1~i位置所有元素的和，因为这里元素下标从1开始，所以注意创建数组要多开一个位置，这里假设我们创建了一个num原数组，和f前缀和数组

那么对于下面的公式应该不难理解，每次计算新位置的前缀和，只要用前一个位置的和加上当前位置的元素即可，那么对于第1个位置的前缀和就等于本身，但是因为会出现f[0]，如果不用vector创建数组的话，要手动将f[0]置为0

了解了公式之后，代码的编写也变得简单了，顺着思路创建两个数组，对于每次查询，只要知道左右位置的下标即可，这里要注意，因为区间包含左右端点，所以实际是f[right]-f[left-1]

代码部分

注意前缀和可能int越界，所以用long long类型防止出现越界

#include <iostream> using namespace std; #include<vector> int main() { int n,m; cin>>n>>m; vector<int> num(n+1); vector<long long> f(n+1); int left,right; f[0]=0; for(int i=1;i<=n;i++){ cin>>num[i]; } for(int j=1;j<=n;j++){ f[j]=f[j-1]+num[j]; } for(int k=1;k<=m;k++){ cin>>left>>right; cout<<f[right]-f[left-1]<<"\n"; } return 0; }

2.二维前缀和

【模板】二维前缀和_牛客题霸_牛客网

刚才是一维的前缀和，这里进行了升维，返回一块矩阵的元素和

其实思路还是一样的，创建两个矩阵，一个原矩阵，一个前缀和矩阵，只不过这个前缀和我们需要分析一下怎么计算

我画了一个三行四列的矩阵，注意下标，仍然是从1开始，所以外层的蓝色矩阵和内层黑色矩阵之间的部分全部要是0才不会影响计算

然后就是查询的操作，例如某次查询输入22，34

注意这里我们要包含的矩阵部分是红色框部分，对于22和34的位置是蓝色箭头的交汇点，所以输入坐标之后取到的元素是坐标往左上角的第一个，也就是图中的6和12，那么就需要计算由6和12作为首尾的一个矩阵和，结果应该是54

讲解完坐标的细节，就进入前缀和的计算

例如某个元素处在D位置，我们如果计算该位置的前缀和呢，我们将矩阵从00到D位置进行分割，出现了四块区域，假设创建了一个原矩阵num和前缀和矩阵dp

所以对于ABCD四块区域的和，也就是A+B+C+D=dp[i][j]，注意到BC区域的值不方便单独计算，但是A+B和A+C可以公式，也就是A+B=dp[i][j-1]，A+C=dp[i-1][j]，A=dp[i-1][j-1]

所以可以通过A+B+C+D=(A+B)+(A+C)+D-A的公式得出前缀和的公式

dp[i][j]=dp[i-1][j]+dp[i][j-1]+num[i][j]-dp[i-1][j-1]

那么套用公式，从11位置开始逐步计算所有位置的前缀和即可

使用这样的方式得到前缀和矩阵之后，就可以直接通过一次运算得到结果了

这里也需要注意细节，因为我们求的是两个红色元素之间的元素和，也就是黄色部分加上这两个红色部分构成的矩阵，但是光是前缀和相减会少减去B和C，也就是绿色和粉色部分的元素

所以采取合并的方式，将AB和AC合并计算，然后减去这两个部分，因为多减去了一个A所以补上一个A，注意要包含红色的元素，所以A应该是x1-1和y1-1构成的矩阵

有了刚才的铺垫，这里就不再赘述怎么加减了

代码部分

#include <iostream> using namespace std; #include<vector> int main() { int n,m,q; int x1,x2,y1,y2; cin>>n>>m>>q; vector<vector<int>> num(n+1,vector<int>(m+1)); 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++){ cin>>num[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+num[i][j]; } } for(int k=1;k<=q;k++){ cin>>x1>>y1>>x2>>y2; cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<"\n"; } return 0; }

3.寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣（LeetCode）

这道题的目标很简单，从左往右，找到一个位置，它的左侧元素和等于右侧元素和

既然我们学会了前缀和，那么后缀和自然也是同样的，只不过计算顺序是从后往前

所以我们创建两个数组，一个前缀和数组，一个后缀和数组

注意这里比较时是不包含当前位置元素的，所以前缀和对于第i个位置，存储的是前i-1个元素的和，后缀和也是，不能包含当前元素

那么就很简单了，遍历一次数组，每次对前缀和数组与后缀和数组的值进行比较判断即可

代码部分

class Solution { public: int pivotIndex(vector<int>& nums) { int len=nums.size(); vector<int> f(len);//前缀和 vector<int> g(len);//后缀和 f[0]=0; g[len-1]=0; for(int i=1;i<len;i++){ f[i]=f[i-1]+nums[i-1]; } for(int j=len-2;j>=0;j--){ g[j]=g[j+1]+nums[j+1]; } for(int k=0;k<len;k++){ if(f[k]==g[k])return k; } return -1; } };

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

238. 除了自身以外数组的乘积 - 力扣（LeetCode）

这道题目和第三题几乎就是换了一种方式的前缀和以及后缀和

只需要创建一个前缀积数组和一个后缀积数组即可，注意不包含当前位置的元素

代码部分，注意f和g初始化时nums的下标要匹配对于元素

因为前缀积第一个位置前面没有元素，第二个位置要存放nums第一个元素本身，所以将前缀积第一个位置初始化为1即可 ，后缀积最后一个位置同理

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

5.和为K的子数组

560. 和为 K 的子数组 - 力扣（LeetCode）

这道题同样可以使用前缀和的方法做，只不过要加上哈希表的使用

我们分析一下，每遍历到一个位置，只要子数组的结尾是当前位置，是不是绝对不可能和前一个位置重复，因为以前一个位置为结尾的子数组不包含当前位置，所以我们要以当前位置作为子数组的结尾，这样保证了子数组的不重复性

对于目标值k，也就是后半段区间的总和是k，那么前半段总和就是sum-k

所以我们把问题转换成，每次遍历到一个新位置的时候，查找前面的所有位置的前缀和，是否存在sum-k，有几组sum-k就存在几组子数组

这里要注意一点，每次遍历到新位置的时候，当前位置的前缀和不能先入哈希表，因为假如我现在查找到L位置的前缀和是sum-k，那么[L+1，R]这个区间就是满足条件的一个子数组，如果我先把当前位置的前缀和放入哈希表，此时L=R，那么[R+1，R]是不存在这个区间的，会出现逻辑错误

那么如果我当前位置R这个位置的前缀和就等于k呢，就会漏掉一种情况，所以我们提前在哈希表中设置一个hash[0]=1，可以理解为在数组前面额外添加一个位置，这个位置的前缀和是0

然后就是哈希表的设置，每次查找完一次前缀和，将当前位置的前缀和放入哈希表

代码部分

class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> hash; hash[0]=1; int ret = 0; int sum = 0; for (auto e : nums) { sum += e; if (hash.count(sum - k)) ret += hash[sum - k]; hash[sum]++; } return ret; } };

6.和可被K惩处的子数组

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

这里需要知道一个定理，同余定理

(a-b)%m=0等价于a%m=b%m

简单证明一下，(a-b)/m=k，那么a-b=mk，推出a=mk+b，两边同时对k取余

a%k=b%k+mk%k，因为mk%k=0，所以a%k=b%k

那么知道这个定理我们可以怎么解题呢

如下图，当前位置的前缀和是sum，如果sum和前面某个前缀和p是同余的，那么可以得出sum-p可以被k整除，所以这里的哈希表我们每次存入前缀和对k取余的结果，然后让sum也取余去查找

这里还需要注意一点，在C++计算余数时，如果前面的数字是负数，余数也是负数，但是不符合我们的要求，我们的余数要是非负数，例如-7%5=-2，而实际上应该是-2*5+3=-7，也就是余数为3，所以我们要让余数加上k，但是这样原本正确的余数就多了一个k，只需要再%k即可去掉多余结果

代码部分

class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int, int> hash; int sum = 0; int ret = 0; hash[0] = 1; for (auto e : nums) { sum += e; int r = (sum % k + k) % k; if (hash.count(r)) ret += hash[r]; hash[r]++; } return ret; } };

7.连续数组

525. 连续数组 - 力扣（LeetCode）

这道题因为只有0和1，我们可以将0进行数值的替换，换成-1，但是这并不影响结果，因为只有元素A和B，保证AB数量相等即可，对AB的值没有要求（不过AB不能相等），这样替换有一个好处，那就是计算前缀和的时候，-1和1会进行抵消

那么我们就可以根据这个特性得出，如果某两个位置的前缀和相等，那么它们中间是不是一定进行了等数量的+1和-1，就可以确定这个区间肯定是-1和1数量相等

注意，对于前缀和相等的L位置和R位置，区间是[L+1，R]这一段

那么逻辑就简单了，每次得到前缀和，就去前面找和它相等的前缀和，取最大值即可

不过还有一点要注意的是，对于所有相等的前缀和，我们应该取最左侧的哪个，这样才是最长

代码部分

class Solution { public: int findMaxLength(vector<int>& nums) { for(auto& e:nums){ if(e==0)e=-1; } int len=nums.size(); unordered_map<int,int> hash; //第一个int表示前缀和，第二个表示下标 //记录每种前缀和的最左下标 hash[0]=-1; int sum=0; int maxn=0; for(int i=0;i<len;i++){ sum+=nums[i]; if(!hash.count(sum))hash[sum]=i; else maxn=i-hash[sum]>maxn?i-hash[sum]:maxn;//三目运算 } return maxn; } };