数组求和统计

[编程题]数组求和统计

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

牛牛有两个长度为 $n$ 的数组 $a, b$ ，牛牛希望统计有多少数对 $(l, r)$ 满足：

1， $0 \leq l \leq r \leq n - 1$

2， $\sum_{i= l}^{r}{a_i} = b_l + b_r$

示例1

输入

[1,2,3,4],[2,1,4,5]

输出

说明

满足条件的数对有

示例2

输入

[0,0,1,1,1],[2,0,4,3,3]

输出

备注:

算法知识视频讲解

Python 3

ZhongHaoWang

对a数组统计前缀和,假设当前区间为[l,r]，根据题意有pre[r + 1] - pre[l] == bl + br，变换等式为pre[r + 1] - br == bl + pre[l];因此我们倒序遍历b数组,枚举其左边界,同时统计pre[r + 1] - br的个数即可

import collections
class Solution:
    def countLR(self , a , b ):
        # write code here
        pre = [0]
        for i in range(len(a)):
            pre.append(pre[-1] + a[i])
        v = collections.defaultdict(int)
        ans = 0
        for i in range(len(b) - 1,-1,-1):
            v[pre[i + 1] - b[i]] += 1
            cur = b[i] + pre[i]
            ans += v[cur]
        return ans

发表于 2021-08-28 10:29:47 回复(0)