枚举+优化(7)——前缀和1

例1

 给定一个长度为N的数组:A1,A2,...,AN。(N <= 100000,1 <= A[i] <= 100000)。然后有M个询问,每次询问给两个整数L,R问A[L]~A[R]的和是多少。(M <= 100000)。  这道题最直接的做法就是每次询问的时候,用一个循环累加A[L]~A[R]的和,伪代码如下:

Ask(L,R)
Sum = 0
For i = L...R
    Sum += A[i]
return Sum

 上面这段伪代码,处理一个询问的时间复杂度是O(R-L),考虑到R最大是N,L最小是1,所以可以认为是O(N)。而通过前缀和,我们可以把每次询问的复杂度降到O(1)

思路

 假设我们有这么一个数组:A = [A1,A2,...,AN]。我们将A[i]加到A[j]的和称为部分和,记作S[i,j],上面的题目就是询问M次部分和。为了减少计算部分和的复杂度,我们先计算出前缀和:S[i] = A[1] + A[2] + ... + A[i]。前缀和可以通过递推的方法O(N)求出来

S[0] = 0
For i = 1...N
    S[i] = s[i-1] + A[i]

 我们看下图,第一排[1,2,5,4,3]是A数组,第二排[0,1,3,8,12,15]就是前缀和。当我们有了前缀和,想要计算S[i,j] = A[i] + A[i+1] + ... + A[j]的时候,直接用S[j] - S[i-1]就行了,比如我们要算A[2]+A[3]+A[4] = 2+5+4=11,只要算S[4]-S[1]=12-1=11即可

 所以我们利用前缀和就可以把计算部分和的复杂度降到O(1),只用计算一次减法。注意A数组是从下标1开始的,但是前缀和数组是从下标0开始的,并且S[0]的值0。这样可以在计算从A1开始的部分和时也不会出问题,例如A1+A2+A3=S[3]-S[0] = 8-0=8。

例2.K倍区间

思路1 暴力枚举

Ans = 0
For i = 1...N
    For j = i...N
        Sum = 0
        For p = i...j
            Sum += A[p]
            If Sum % k == 0
                Ans++

 这个算法的时间复杂度是O(N^3^)。

思路2 前缀和优化

 优化的思路就是先把部分和,转换成前缀和的差。题目要求A[i]+A[i+1]+…+A[j]是K的倍数,等价于S[j]-S[i-1]是K的倍数,等价于S[j]与S[i-1]模K余数相等。所以我们可以还是2重循环枚举i和j,但是直接用前缀和判断是不是K的倍数:

Ans = 0
For i = 1...N
    For j = i...N
        If (S[j] - S[i - 1]) % k == 0
            Ans++

 优化之后的复杂度是O(N^2),还不足够优秀,还是会超时。我们再进一步分析一下要求的答案和前缀和的关系,看一下下面这张图:

 图中的第一排[1, 2, 5, 4, 3]是A数组。绿色的第二排是前缀和,天蓝色的第三排是前缀和%K之后的结果,这里我们假设K=2。  我们之前的算法,实际上就是在第三排的数组里,找两个相等的值(这里解释一下为什么是找相等的值,因为如果两个值相等,那么s[j] - s[i-1]=0,0%k=0)。每一对相等的值,都对应着一个K倍区间。比如第三排有3个0,第一个0和第二个0,对应[1, 2, 5]这个区间;第一个和第三个0,对应[1, 2, 5, 4]这个区间;第二个和第三个0,对应[4]这个区间。  所以我们已知第三排数组有3个0和3个1的情况下,可以直接用组合数求出来K倍区间的数目:C(3,2)+C(3, 2)=6。C(3, 2)是指从3个物品里取出2个来的组合数。因为有3个0和3个1,所以答案就是C(3, 2)+C(3, 2)。  把上面统计的思路归纳一下,就是:计算前缀和S[0], S[1], S[2], … S[N]。统计S[]中模K余0, 1, 2 … K-1的数量,记为cnt[0], cnt[1], cnt[2] … cnt[K-1]。答案就是:cnt[0]×(cnt[0]-1)/2 + cnt[1]×(cnt[1]-1)/2 +… +cnt[K-1]×(cnt[K-1]-1)/2

#include <iostream>
#include <unordered_map>
using namespace std;
int n,k,a[100001],s[100001];
unordered_map<int,int> cnt;
//cnt[0]存储的是余数是0的前缀和有几个
//cnt[1]存储的是余数是1的前缀和有几个
//以此类推
int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    s[0] = 0;
    cnt[0] = 1;
    for(int i = 1;i <= n;i++)
    {
        s[i] = (s[i-1] + a[i]) % k;
        cnt[s[i]]++;
        //一边求前缀和
        //一边统计前缀和模K的余数出现了多少次
    }
    long long ans = 0;
    //根据每个余数出现的次数用组合数求答案
    for(int i = 0;i < k;i++)
        ans += (long long)(cnt[i]) * (cnt[i] - 1) / 2;
    //把答案累加上C(cnt[i], 2)
    //也就是cnt[i]*(cnt[i]-1)/2
    cout << ans;
    return 0;
}

 上面的程序既用到了前缀和优化,也用了哈希表统计每个前缀和余数出现的次数。总复杂度是O(N+K)

例2 K的倍数

 我们要找到最长的K倍区间。实际上就是找到前缀和余数最左边和最右边的0的位置,算一下长度;再找到最左边和最右边的1的位置,算一下长度……最后找到最左边和最右边K-1的位置,算一下长度。最终取其中最长的区间就是答案。

#include <iostream>
#include <unordered_map>
using namespace std;
int n,k,a[100001],s[100001];
unodered_map<int.int>lmost.rmost;
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    cin >> k;
    for(int i = 1;i <= n;i++)
    {
        lmost[i] = n + 1;
        rmost[i] = -1;
    }
    s[0] = 0;
    lmost[0] = rmost[0] = 0;
    for(int i = 1;i <= n;i++)
    {
        //一边计算前缀和
        //一边更新余数的最左位置和最右位置
        s[i] = (s[i-1] + a[i]) % k;
        if(lmost[s[i]] > i)
            lmost[s[i]] = i;
        if(rmost[s[i]] < i)
            rmost[s[i]] = i;
    }
    int ans = 0;
    //根据每个余数出现的次数用组合数求答案
    //前缀和都余i的对应的区间长度
    for(int i = 0;i < k;i++)
        ans = rmost[i] - lmost[i];
    cout << ans;
    return 0;
}

 我们用lmost和rmost保存第一个前缀和余数最左和最右的下标。整个程序复杂度也是O(n+k)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏转载gongluck的CSDN博客

python笔记:#010#运算符

运算符 目标 算数运算符 比较(关系)运算符 逻辑运算符 赋值运算符 运算符的优先级 数学符号表链接:https://zh.wikipedia.org/wiki...

3546
来自专栏Golang语言社区

第七节 Go语言运算符

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

963
来自专栏古时的风筝

风筝的C++随时记

关于常量指针和指针常量 两个概念经常混淆啊,这是在考中文四六级啊,所以我给这两个概念起个长一点的名字。 常量指针 = 指向常量的指针 指针常量 = 指针是一个常...

1798
来自专栏Linux驱动

汇编指令-CMP、TEQ(5)

 cmp:(compare)指令进行比较两个操作数的大小  格式: cmp oprd1,oprd2 比较oprd1和oprd2操作数,然后通过助记符来实现想要的...

17810
来自专栏c#开发者

biztalk rosettanet 自定义 pip code

USE [BTARNDATA] GO /****** Object: StoredProcedure [dbo].[proc_GetActivityStatu...

25711
来自专栏WindCoder

《简明 Python 教程》学习笔记-运算符与表达式

又两天没更新了,暂且同步两篇之前的笔记。运算符与表达式这一块感觉主要就是运算符与它们的用法以及优先级了。

662
来自专栏C/C++基础

不用加号实现两整数相加

对于二进制的加法运算,若不考虑进位,则1+1=0,1+0=1,0+1=1,0+0=0,通过对比异或,不难发现,此方法与异或运算类似。因而排出进位,加法可用异或来...

382
来自专栏小狼的世界

用PHP实现的四则运算表达式计算

这个实现方式中使用了两个堆栈,一个用来存储数字,一个用来存储运算符,遇到括号以后就递归进入括号内运算,实现方式有点笨拙,后面补充一下“逆波兰表达式”的算法实现。...

813
来自专栏HelloCode开发者学习平台

BAT面试算法进阶(2)-两数相加

You are given two non-empty linked lists representing two non-negative integ...

932
来自专栏Golang语言社区

Go 语言运算符

运算符用于在程序运行时执行数学或逻辑运算。 Go 语言内置的运算符有: 算术运算符 关系运算符 逻辑运算符 位运算符 赋值运算符 其他运算符 接下来让我们来详细...

3287

扫码关注云+社区