★ 算法OJ题 ★ 前缀和算法（上）

Ciallo～(∠・ω< )⌒☆ ~ 今天，将和大家一起做几道前缀和算法题 ~

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页：椎名澄嵐-CSDN博客

算法专栏：★ 优选算法100天 ★_椎名澄嵐的博客-CSDN博客

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

壹【模板】一维前缀和

1.1 题目

1.2 算法解析

1.3 撰写代码

贰【模板】二维前缀和

2.1 题目

2.2 算法解析

2.3 撰写代码

叁寻找数组的中心下标

3.1 题目

3.2 算法解析

3.3 撰写代码

肆除自身以外数组的乘积

4.1 题目

4.2 算法解析

4.3 撰写代码

壹【模板】一维前缀和

1.1 题目

【模板】前缀和_牛客题霸_牛客网

1.2 算法解析

1.3 撰写代码

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

int main() 
{
    // 读取数据
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    // 预处理前缀和数组
    vector<long long> dp(n + 1);
    for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];//此处有溢出风险
    // 使用前缀和数组
    int l = 0, r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

贰【模板】二维前缀和

2.1 题目

【模板】二维前缀和_牛客题霸_牛客网

2.2 算法解析

2.3 撰写代码

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

int main() 
{
    // 读入数据
    int n = 0 , m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; 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 - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
    // 使用前缀和矩阵
    int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

叁寻找数组的中心下标

3.1 题目

724. 寻找数组的中心下标 - 力扣（LeetCode）

3.2 算法解析

3.3 撰写代码

class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n);
        vector<int> 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;
    }
};

肆除自身以外数组的乘积

4.1 题目

238. 除自身以外数组的乘积 - 力扣（LeetCode）

4.2 算法解析

4.3 撰写代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<long long> f(n), g(n);
        // 预处理前缀积和后缀积
        f[0] = g[n - 1] = 1;
        for (int i = 1; i <= n - 1; 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];
        // 使用前缀积和后缀积
        vector<int> ret(n);
        for (int i = 0; i <= n - 1; i++)
            ret[i] = f[i] * g[i];
        return ret;
    }
};