多多的求和计算

[编程题]多多的求和计算

热度指数：8693 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。

多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。
现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。

输入描述:

第一行，有2个整数N和M，表示树的数量以及计算和谐值的参数。
（ 1 <= N <= 100,000, 1 <= M <= 100  ）
第二行，有N个整数Ai, 分别表示第i个颗树的和谐值。
（ 0 <= Ai <= 1,000,000,000 ）

输出描述:

共1行，每行1个整数，表示满足整体是和谐的区间的数量。

示例1

输入

5 2
1 2 3 4 5

输出

说明

长度为1: [2], [4]
长度为2: 无
长度为3: [1,2,3], [3,4,5]
长度为4: [1,2,3,4], [2,3,4,5]
长度为5: 无
共6个区间的和谐值之和可以被2整除。

备注:

对于50%的数据，有N<=1,000
对于100%的数据，有N<=100,000

算法知识视频讲解

JavaScript

牛客645135900号

var firstline=readline().split(" ")
var listlen=parseInt(firstline[0])
var harmonum=parseInt(firstline[1])
var list=readline().split(" ")
var lista=list.map(item=>parseInt(item))
//存放0-i位置的数组和的余数
var leftnum=[]
var sumtmp=0
var ans=0
//存放某个余数的出现个数
var map=new Map([[0,0]])
for(var i=0;i<listlen;i++){
    sumtmp+=lista[i]
    if(sumtmp%harmonum==0){ans+=1}
    if(!map.has(sumtmp%harmonum)){
        map.set(sumtmp%harmonum,1)
    }else{
        ans+=map.get(sumtmp%harmonum)
        map.set(sumtmp%harmonum,map.get(sumtmp%harmonum)+1)
    }
}
console.log(ans)

js版本

发表于 2022-04-11 16:11:38 回复(0)