【算法刷题指南】前缀和

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站

在这里插入图片描述

🌈个人主页：南桥几晴秋
🌈C++专栏：南桥谈C++
🌈C语言专栏： C语言学习系列
🌈Linux学习专栏：南桥谈Linux
🌈数据结构学习专栏：数据结构杂谈
🌈数据库学习专栏：南桥谈MySQL
🌈Qt学习专栏：南桥谈Qt
🌈菜鸡代码练习：练习随想记录
🌈git学习：南桥谈Git

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 本科在读菜鸡一枚，指出问题及时改正

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站

文章目录

DP34 【模板】前缀和
DP35 【模板】二维前缀和
724.寻找数组的中心下标
238.除自身以外数组的乘积
974.和可被 K 整除的子数组
560.和为k的子数组
525.连续数组
1314.矩阵区域和

DP34 【模板】前缀和

#include<iostream>using namespace std;
typedef long long ll ;
const int N=100005;
ll arr[N],sum[N];
ll n,q,l,r;int main()
{cin>>n>>q;for(int i=1;i<=n;i++) cin>>arr[i];//预处理一个前缀和数组for(int i=1;i<=n;i++) sum[i]=sum[i-1]+arr[i];//使用这个前缀和数组while(q--){cin>>l>>r;cout<<sum[r]-sum[l-1]<<endl;}return 0;
}

DP35 【模板】二维前缀和

#include<iostream>using namespace std;
typedef long long ll;
const int N=1005;
int m,n,q;
ll arr[N][N],sum[N][N];int main()
{cin>>n>>m>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>arr[i][j];sum[i][j]=sum[i-1][j]+sum[i][j-1]+arr[i][j]-sum[i-1][j-1];}int x1,y1,x2,y2;while (q--) {cin>>x1>>y1>>x2>>y2;cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 -1] <<endl;}return 0;
}

724.寻找数组的中心下标

class Solution {
public:int pivotIndex(vector<int>& nums) {int n=nums.size();vector<int> lsum(n),rsum(n);for(int i=1;i<n;i++)lsum[i]=lsum[i-1]+nums[i-1];for(int i=n-2;i>=0;i--)rsum[i]=rsum[i+1]+nums[i+1];for(int i=0;i<n;i++){if(lsum[i]==rsum[i])return i;}return -1;}
};

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

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

974.和可被 K 整除的子数组

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

560.和为k的子数组

560.和为k的子数组添加链接描述

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

525.连续数组

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0]=-1;int sum=0,ans=0;for(int i=0;i<nums.size();i++){nums[i]=nums[i]==0?-1:1;sum+=nums[i];if(hash.count(sum)) ans=max(ans,i-hash[sum]);else hash[sum]=i;}return ans;}
};

1314.矩阵区域和

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m=mat.size(),n=mat[0].size();vector<vector<int>> sum(m+1,vector<int>(n+1));for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i-1][j-1];vector<vector<int>> ans(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;ans[i][j]=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];}return ans;}
};