【数据结构与算法】前缀和
【数据结构与算法】前缀和
前言
这是我自己学习蓝桥杯算法的第四篇博客总结。 上一期笔记是关于二分查找算法，没看的同学可以过去看看： 【数据结构与算法】二分查找_.二分查找c++-CSDN博客
https://cloud.tencent.com/developer/article/2519670
技巧
一维数组前缀和
前缀和算法：快速求出数组中某一连续区间的和。 原来的数组为numsn，新创建一个前缀和数组dpn，则有dpi=dpi-1+numsi。 如果原来的数组下标是从1开始，那么前缀和数组下标也从1开始，可以避免处理边界条件。 前缀和也可以变形成后缀和。
二维数组前缀和
前缀和算法：快速求出数组中某一矩阵区间的和。 原来的数组为numsn，新创建一个前缀和数组dpn，则有dpn=dpn-1+dpn+numsn-dpn-1。 如果原来的数组下标是从1开始，那么前缀和数组下标也从1开始，可以避免处理边界条件。
例题
nowcoder-dp34题：undefined【模板】前缀和_牛客题霸_牛客网
#include <iostream>
using namespace std;
int main()
{
int n=0,m=0,l=0,r=0;
long long arr[100001]={0};
long long dp[100001]={0};
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>arr[i];
for(int i=1;i<=n;i++)
dp[i]=dp[i-1]+arr[i];
while(m--)
{
cin>>l>>r;
cout<<dp[r]-dp[l-1]<<endl;
}
return 0;
}nowcoder-dp35题：undefined【模板】二维前缀和_牛客题霸_牛客网
#include <iostream>
using namespace std;
int main()
{
int n=0,m=0,q=0;
long long nums[2000][2000]={0};
long long dp[2000][2000]={0};
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>nums[i][j];
}
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]+nums[i][j];
}
while(q--)
{
int x1=0,y1=0,x2=0,y2=0;
cin>>x1>>y1>>x2>>y2;
long long ret=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
cout<<ret<<endl;
}
return 0;
}leetcode-724题：undefined724. 寻找数组的中心下标 - 力扣（LeetCode）
https://leetcode.cn/problems/find-pivot-index/description/
class Solution {
public:
int pivotIndex(vector<int>& nums)
{
int left=0,right=nums.size(),cur=0;
int dp[20000]={0};
dp[0]=nums[0];
for(int i=1;i<right;i++)
{
dp[i]=dp[i-1]+nums[i];
}
while(cur<right)
{
if(cur==0&&0==dp[right-1]-dp[cur])
return 0;
else if(cur!=0&&dp[cur-1]==dp[right-1]-dp[cur])
return cur;
else
cur++;
}
return -1;
}
};leetcode-238题：undefined238. 除自身以外数组的乘积 - 力扣（LeetCode）
https://leetcode.cn/problems/product-of-array-except-self/
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums)
{
int end=nums.size()-1;
vector<int> dp_front(nums.size(),0);
vector<int> dp_back(nums.size(),0);
vector<int> answer(nums.size(),0);
dp_front[0]=nums[0];
dp_back[end]=nums[end];
for(int i=1;i<=end;i++)
dp_front[i]=dp_front[i-1]*nums[i];
for(int i=end-1;i>=0;i--)
dp_back[i]=dp_back[i+1]*nums[i];
answer[0]=dp_back[1];
answer[end]=dp_front[end-1];
for(int i=1;i<end;i++)
answer[i]=dp_front[i-1]*dp_back[i+1];
return answer;
}
};leetcode-560题： 560. 和为 K 的子数组 - 力扣（LeetCode）
https://leetcode.cn/problems/subarray-sum-equals-k/description/
class Solution {
public:
int subarraySum(vector<int>& nums, int k)
{
unordered_map<int,int> m;
m[0]=1;
int count=0,i=0,sum=0;
while(i<nums.size())
{
sum+=nums[i];
int remainder=sum-k;
if(m.find(remainder)!=m.end())
count+=m[remainder];
m[sum]++;
i++;
}
return count;
}
};leetcode-974题： 974. 和可被 K 整除的子数组 - 力扣（LeetCode）
https://leetcode.cn/problems/subarray-sums-divisible-by-k/
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k)
{
unordered_map<int,int> m;
m[0]=1;
int sum=0,i=0,count=0;
while(i<nums.size())
{
sum+=nums[i];
int remainder=(sum%k+k)%k;
if(m.find(remainder)!=m.end())
count+=m[remainder];
m[remainder]++;
i++;
}
return count;
}
};leetcode-525题：525. 连续数组 - 力扣（LeetCode）
https://leetcode.cn/problems/contiguous-array/
class Solution {
public:
int findMaxLength(vector<int>& nums)
{
unordered_map<int,int> m;
int length=0,i=0,sum=0;
m[0]=0;
while(i<nums.size())
{
if(nums[i]==0)
sum+=-1;
else
sum+=1;
if(m.find(sum)!=m.end())
length=max(length,i+1-m[sum]);
else
m[sum]=i+1;
i++;
}
return length;
}
};
腾讯云开发者
