题目描述

难度分:$726$

输入$n(1 \leq n \leq 2 \times 10^5)$，$k(-10^{15} \leq k \leq 10^{15})$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

输出元素和等于$k$的连续子数组个数。

输入样例$1$

6 5
8 -3 5 7 0 -4

输出样例$1$

3

输入样例$2$

2 -1000000000000000
1000000000 -1000000000

输出样例$2$

0

算法

前缀和+哈希表计数

思路类似于“两数之和”，用一个哈希表$mp$记录每个前缀和的出现次数。遍历数组，如果遍历到$i$时，对应的前缀和为$presum$，并且它前面出现过$mp[presum-k]$次前缀和$presum-k$，那么这些位置$j$，就都满足子数组$(j,i]$的累加和为$k$，因此以$i$结尾累加和为$k$的子数组有$mp[presum-k]$个。

遍历完整个数组就能得到以任意一个元素结尾时能够产生的“累加和为$k$的子数组”数量。需要注意的是，在遍历之前要初始化$mp[0]=1$，因为刚开始一个元素都没有，只有一个$0$的前缀和。

复杂度分析

时间复杂度

遍历了一遍数组，中间的哈希表操作都是$O(1)$的，因此算法整体的时间复杂度为$O(n)$。

空间复杂度

哈希表是唯一的额外空间消耗，最差情况下每个位置都是一个不同的前缀和，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, a[N];
LL k;

int main() {
    scanf("%d%lld", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    unordered_map<LL, int> mp;
    mp[0] = 1;
    LL presum = 0, ans = 0;
    for(int i = 1; i <= n; i++) {
        presum += a[i];
        LL x = presum - k;
        if(mp.count(x)) ans += mp[x];
        mp[presum]++;
    }
    printf("%lld\n", ans);
    return 0;
}