【算法笔记】前缀和算法原理深度剖析（超全详细版）

【算法笔记】前缀和算法原理深度剖析（超全详细版）

🔥个人主页：大白的编程日记

🔥专栏：算法笔记

前言

哈喽，各位小伙伴大家好！上期我们讲了二分算法。今天我们来讲前缀和的算法原理。话不多说，咱们进入正题！向大厂冲锋！

一.一维前缀和

1.1题目

• 题目:【模板】前缀和
  

1.2算法原理解析

我们根据前缀和算法就可以快速求出区间和。

为了防止越界，我们要让前缀和数组下标从1开始。

1.3代码实现

#include <iostream>
#include<vector>
using namespace std;
int main() 
{
    int n,q;
    cin>>n>>q;
    vector<long long> dp(n+1);//多开一个节点防止越界
    int tmp=0;
    for(int i=1;i<=n;i++)
    {
        cin>>dp[i];
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]+=dp[i-1];
    }
    int l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
}
// 64 位输出请用 printf("%lld")

二.二维前缀和

2.1题目

• 题目:二维前缀和

2.2算法原理解析

2.3下标映射

2.4初始化问题

如果用到两个前缀和区间求某区间的和
我们初始化的值并不重要。

• 验证
  
  

2.5代码实现

#include <iostream>
#include<vector>
using namespace std;

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> arr(n,vector<long long>(m));
    for (int i = 0; i <n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }
    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++)
        {
            dp[i][j] = dp[i][j - 1]+dp[i-1][j]-dp[i-1][j-1]+arr[i-1][j-1];
        }
    }
    while (q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        long long sum=0;
        sum=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
        cout<<sum<<endl;
    }
}

三.寻找数组的中心下标

3.1题目

• 题目：寻找数组的中心下标
  

3.2思路分析

这里我们借助前缀和数组和后缀和数组即可快速判断中心下标。

3.3代码实现

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

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

4.1题目

• 题目：除自身以外数组的乘积
  

4.2思路分析

4.3总结

4.4代码实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int> f(n),g(n),ret(n);
        f[0]=g[n-1]=1;
        for(int i=1;i<n;i++)//前缀和数组
        {
            f[i]=f[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--)//后缀和数组
        {
            g[i]=g[i+1]*nums[i+1];
        }
        for(int i=0;i<n;i++)
        {
            ret[i]=f[i]*g[i];
        }
        return ret;
    }
};

五.和为k的子数组

5.1题目

• 题目：和为k的子数组
  

5.2思路分析

5.3代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0]=1;//整个区间和为k
        int sum=0,ret=0;
        for(auto e:nums)
        {
            sum+=e;//计算前缀和
            if(hash.count(sum-k))//统计和为sum-k区间个数
            {
                ret+=hash[sum-k];
            }
            hash[sum]++;//填入前缀和信息
        }
        return ret;
    }
};

六.和可被k整除的子数组

6.1题目

• 题目：和可被k整除的子数组
  

6.4思路分析

关于更多的模运算知识可以看一下灵神的这篇讲解：
模运算的世界

6.3代码实现

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0]=1;//整个区间和为k
        int sum=0,ret=0;
        for(auto e:nums)
        {
            sum+=e;//计算前缀和
            if(hash.count((sum%k+k)%k))//统计和为被k整除区间个数负数修正
            {
                ret+=hash[(sum%k+k)%k];
            }
            hash[(sum%k+k)%k]++;//填入前缀和%k信息
        }
        //(a-b)%p==a%p==b%p同余定理
        return ret;
    }
};

七.连续数组

7.1题目

• 题目：连续数组
  

7.1思路分析

7.3代码实现

class Solution {
public:
    int findMaxLength(vector<int>& nums)
    {
        unordered_map<int,int> hash;
        hash[0]=-1;
        int sum=0,len=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=(nums[i]==0?-1:1);//0就变成-1；
            if(hash.count(sum-0))
            {
                len=max(len,i-hash[sum]);//更新长度
            }
            else//相同的前缀和不更新
            {
                hash[sum]=i;//更新哈希表前缀和信息
            }
        }
        return len;
    }
};

八.矩阵区域和

8.1题目

• 题目：矩阵区域和
  

8.2思路分析

8.3代码实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
    {
        int m=mat.size(),n=mat[0].size();
        vector<vector<int>> arr(m+1,vector<int>(n+1));
        for(int i=1;i<m+1;i++)//处理前缀和数组
        {
            for(int j=1;j<n+1;j++)
            {
                arr[i][j]=arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1]+mat[i-1][j-1];
            }
        }
        vector<vector<int>> arr1(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;
                int x2=min(m-1,i+k)+1;
                int y1=max(0,j-k)+1;
                int y2=min(n-1,j+k)+1;//计算下标 +1映射dp数组
                arr1[i][j]=arr[x2][y2]-arr[x2][y1-1]-arr[x1-1][y2]+arr[x1-1][y1-1];
            }
        }
        return arr1;
    }
};

后言

这就是前缀和算法原理的深度剖析。大家自己好好消化理解。今天 就分享到这，感谢各位大耐心垂阅！咱们下期见！拜拜~