【算法】前缀和

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

文章目录

引言
一、一维前缀和
二、二维前缀和
三、寻找数值的中心下标
四、除自身以外数组的乘积
五、和为k的子数组
六、和可被k整除的子数组
七、连续数组
八、矩阵区域和
总结

引言

前缀和，实际上是一种非常简单的动态规划，通过预处理前缀和数组，以空间换时间，提高运行效率。

一、一维前缀和

思路：

状态表示：dp[i] 为 [1,i] 区间的前缀和（为了方便表示，下标从1开始）
状态转移方程：dp[i] = dp[i-1] + v[i];
使用前缀和数组：dp[r] - dp[l-1]（表示从l到r的区间和）

int main()
{
    int n, q, l, r;
    cin >> n >> q;
    vector<int> v(n+1);
    vector<long> dp(n+1);
    for(int i=1; i<=n; ++i)
    {
        cin >> v[i];
        dp[i] = dp[i-1] + v[i];
    }

    while(q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l-1] <<endl;
    }
    return 0;
}

二、二维前缀和

思路：

状态表示：dp[i][j] 为 (1,1) 到 (i, j) 区间的前缀和
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1] + vv[i][j] - dp[i-1][j-1];
使用前缀和数组：dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

int main()
{
    int m, n, q;
    cin >> m >> n >> q;
    vector<vector<int>> vv(m+1, vector<int>(n+1));
    vector<vector<long long>> dp(m+1, vector<long long>(n+1));       
    for(int i=1; i<m+1; ++i)
    {
        for(int j=1; j<n+1; ++j)
        {
            cin >> vv[i][j];
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + vv[i][j] - dp[i-1][j-1];
        }
    }

    while(q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;
    }
    return 0;
}

三、寻找数值的中心下标

思路：

创建前缀和数组f 和后缀和数组g
状态表示：f[i]代表[0,i-1]区间的前缀和，g[i]代表[i+1,n-1]区间的后缀和
f[i] = f[i-1] + nums[i-1]; g[i] = g[i+1] + nums[i+1];

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] = 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)
            if(f[i] == g[i])
                return i;
        return -1;
    }
};

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

思路：

创建前缀积数组f 和后缀积数组g
状态表示：f[i]代表[0,i-1]区间的前缀积，g[i]代表[i+1,n-1]区间的后缀积
f[i] = f[i-1] * nums[i-1]; g[i] = g[i+1] * nums[i+1];

class Solution
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1), ans(n);
        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)
            ans[i] = f[i] * g[i];
        return ans;
    }
};

五、和为k的子数组

思路：前缀和 + 哈希表

状态表示：dp[i] 代表以i为结尾的区间中和为k的子数组个数
在以i为结尾的区间中，寻找和为dp[i]-k的前缀和，统计个数
无需创建前缀和数组，只需用sum变量维护即可
为了快速查找，创建哈希表countMap存储前缀和
处理边界（sum == k）：countMap[0] = 1;
先统计，再将当前前缀和存入哈希表

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

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

思路：前缀和 + 哈希表

本题与上题思路类似
同余定理：（a-b）% k == 0 等价于 a%k == b%k
（sum-x）% k == 0 等价于 sum%k == x%k（x为之前的前缀和）
正负取模统一：(sum % k + k) % k
创建哈希表countMap存储前缀和的余数

class Solution
{
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        unordered_map<int, int> countMap;
        countMap[0] = 1;

        int sum = 0, count = 0;
        for(auto n : nums)
        {
            sum += n;
            int target = (sum % k + k) % k;
            if(countMap.count(target)) count += countMap[target];
            ++countMap[target];
        }
        return count;
    }
};

七、连续数组

思路：前缀和 + 哈希表

将0改成-1，转化为和为0的子数组
哈希表存储<前缀和，长度>
处理sum == k的边界情况：countMap[0] = -1；
哈希表中只存当前值对应长度最短的前缀和（为了求最长的子数组）

class Solution
{
public:
    int findMaxLength(vector<int>& nums)
    {
        //转化：和为0的子数组
        unordered_map<int, int> countMap;//存储<前缀和,长度>
        countMap[0] = -1;//处理sum == k的边界情况

        int sum = 0, len = 0, n = nums.size();
        for(int i=0; i<n; ++i)
        {
            sum += nums[i] == 0 ? -1 : 1;//将0变成-1，才能转化
            if(countMap.count(sum)) len = max(len, i-countMap[sum]);
            else countMap[sum] = i;//存在代表下标更小，不用更新；不存在才要插入
        }
        return len;
    }
};

八、矩阵区域和

思路：

二维前缀和
因为dp矩阵下标从1开始，而原始矩阵下标从0开始，所以注意下标映射关系
为了防止越界，求坐标时用max和min函数与边界比较

class Solution
{
public:
    int dp[110][110] = {0};
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
    {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> ans(m, vector<int>(n));
        //预处理前缀和矩阵
        for(int i=1; i<=m; ++i)
        {
            for(int j=1; j<=n; ++j)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }
        //使用前缀和矩阵
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                x1 = max(0, i-k) + 1, y1 = max(0, j-k) + 1;
                x2 = min(m-1, i+k) + 1, y2 = min(n-1, j+k) + 1;
                ans[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }
        return ans;
    }
};