#AcWing：前缀和的应用

最新推荐文章于 2025-04-17 11:42:57 发布

fff_421

最新推荐文章于 2025-04-17 11:42:57 发布

阅读量156

点赞数

分类专栏： leetcode & AcWing 文章标签： leetcode

本文链接：https://blog.csdn.net/studyyyyyyyyyy/article/details/117375883

版权

leetcode & AcWing 专栏收录该内容

37 篇文章

订阅专栏

终于稳定复习了，继续更新…
前缀和和前缀乘积很简单了，现在都会了，现在我们看怎么构造这个区间。不是双重遍历左右区间，我们固定右区间变成查表。

AcWing.3574 乘积数量

在这里插入图片描述

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

int main()
{
    int n;
    LL z = 0, f = 0;
    scanf("%d", &n);
    int s = 1, sz = 1, sf = 0;
    
    for(int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        if(a < 0) s *= -1;
        if(s > 0) z += sz, f += sf, sz++;
        else z += sf, f += sz, sf++;
    }
    
    printf("%lld %lld", f, z);
    return 0;
}

AcWing.1230 K倍区间

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;

LL kk[N];
LL s[N];
int main()
{
    int n, k, a;
    LL ans = 0;
    scanf("%d %d", &n, &k);
    kk[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a);
        s[i] = s[i - 1] + a;
        ans += kk[s[i] % k];
        kk[s[i] % k]++;
    }
    printf("%lld", ans);
    return 0;
}

lc523: 连续的子数组和

6.2每日一题
another k倍区间 + 子数组长度至少为2(存储位置即可)

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> kk;
        int s = 0;
        kk[s] = 0;
        for(int j = 1; j <= n; j++)
        {
            s = (s + nums[j - 1]) % k;
            if(kk.find(s) != kk.end() && (j - kk[s]) >= 2)
                return 1;
            if(kk.find(s) == kk.end())
                kk[s] = j;
        }
        return false;
    }

6.3每日一题,又是这个前缀和的改进,终于会了
y总教得好!
这一题的关键在于s1[j] - s1[i - 1] = s0[j] - s0[i - 1],即s1[j] - s0[j] = s1[i - 1] - s0[i - 1],遍历区间的右端点,等式的左侧和右侧其实是一个东西,边遍历便把s1[i - 1] - s0[i - 1]存到哈希表中,判断等式的时候只需要查表就可以了,将复杂度降到了O(n)

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int si = 0, ans = 0; //si = s1[i - 1] - s0[i - 1]
        unordered_map<int, int> len;
        len[si] = 0;
        for(int j = 1; j <= n; j++)
        {
            if(nums[j - 1] == 1) si++;
            else si--;
            if(len.find(si) != len.end())
                ans = max(ans, j - len[si]);
            else
                len[si] = j;
        }
        return ans;
    }
};