webank---9.3---笔试第三题

题目描述：
输入三个整数,n,u,v，n是接下来输入数组的长度，u和v等下再用
再输入一个数组nums
然后求nums的连续子数组有多少个，这个子数组的均值等于u/v

思路：前缀和+hash表

技巧：由于平均数比较麻烦，先将所有元素都乘v然后再减去u，这样方便后面的前缀和（即，原来是avg(子数组)=u/v，我们更改以后是：子数组的和等不等于0），算式是这样的：(x1+x2+……xn) / n= u/v --->（转化成）(x1+x2+……xn)*v -n*u = 0 --->(再化简) (x1*v-u) + (x2*v-u) + (x3*v-u) + …… + (xn*v-u) = 0，将这个数组全新定义为新的nums。接下来的问题就是【LC：和为k的子数组个数】

代码：

while(1):
    line1 = input().strip()
    if len(line1)<=0:break
    line1 = line1.split(' ')
    n,u,v = int(line1[0]),int(line1[1]),int(line1[2])
    line2 = input().strip()
    nums = [int(x) for x in line2.split(' ')]
    def f(nums,u,v):
        nums = [x*v-u for x in nums]
        res = 0
        presum = [0]
        for x in nums:presum.append(presum[-1]+x)
        presum = presum[1:]
        hashset = dict()
        for x in presum:
            # print(x,hashset,res)
            if x==0:res+=1
            if x in hashset:
                res+=hashset[x]
                hashset[x]+=1
            else:hashset[x] = 1
        return res
    print(f(nums,u,v))