【算法刷题指南】前缀和

🕗 发布于 2024-12-14 07:30 c++ 算法前缀和

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

在这里插入图片描述

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

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

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

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;
    }
};