【算法】前缀和问题

_小羊_

发布于 2025-03-29 09:51:45

7500

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

前缀和

前缀和题目做法的核心就两步：预处理前缀和数组 + 使用前缀和数组。
这两步通常需要我们总结出一个递推公式，类似于动态规划。
我们需要明确比如 dp[i] 的含义具体是什么，其中特别需要注意循环的区间。
前缀和 + 哈希表通常可以用来解决：子数组和为特定值、子数组和的频率等问题。

一维前缀和

前缀和

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<ll> arr(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++) 
    {
        cin >> arr[i];
        dp[i] = dp[i - 1] + arr[i];
    }
    int l, r;
    while (q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

二维前缀和

二维前缀和

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
    int n, m, q,x1, x2, y1, y2;
    cin >> n >> m >> q;
    vector<vector<ll>> arr(n + 1, vector<ll>(m + 1)), dp(n + 1, vector<ll>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];
        }
    ll tmp = 0;
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        tmp = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
        cout << tmp << endl;
    }
    return 0;
}

寻找数组的中心下标

寻找数组的中心下标

注意：不是所有一维前缀和数组的递推都是 dp[i] = dp[i - 1] + arr[i]，要根据具体题目具体分析。

本题中的 dp[i] 表示的是 i 位置之前的前缀和，不包括 i 位置，所以 dp 表要多开一个位置，而且还要注意循环的区间。

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

除自身以外数组的乘积

除自身以外数组的乘积

其中 f[i] 和 b[i] 分别表示 i 位置之前、之后所有元素之积。

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

和为 K 的子数组

和为 K 的子数组

从前向后统计数组的前缀和，假设以 i 位置为结尾的子数组有 n 个和为 k，则在 i 位置之前的前缀和中有 n 个和为 sum - k 的前缀和，而我们可以在计算前缀和的过程中在哈希表中记录各前缀和出现的次数。

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 (int e : nums)
        {
            sum += e; // 前缀和
            if (hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

和可被 K 整除的子数组（lqb真题）

和可被 K 整除的子数组

这道题和上道题类似，但是这道题主要考下面两个知识点。

假设以 i 位置为结尾的子数组中有 n 个子数组之和能被 k 整除，有 n 个这样的子数组，也就对应着有 n 个上面的 x 区间。根据同余定理我们只需要求 i 位置前面的所有前缀和中有多少个前缀和的余数等于 sum % k。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 前缀和的余数及其次数
        hash[0] = 1;
        int sum = 0, ret = 0;
        for (int e : nums)
        {
            sum += e;
            int t = (sum % k + k) % k;
            if (hash.count(t)) ret += hash[t];
            hash[t]++;
        }
        return ret;
    }
};