Good Subarrays(前缀和)

题目
题意：给定n个数，每个数大小为0-9，求这n个数，有多少个连续子区间，满足${\sum }_{i=l}^r==(r-l+1)$

思路：每个数都减去1，问题转化为，求有有多少个连续子区间，满足${\sum }_{i=l}^r==0$，只需求出每个前缀和，如果$su{m}_{i=1}^l==su{m}_{i=1}^r$，说明$su{m}_{i=l+1}^r==0$。因此，找出所有前缀和相同的个数x，那么这些前缀和贡献的区间数为$x\ast (x-1)/2$，注意，初始时，$nu{m}_0=1$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100010;

int a[maxn];
char s[maxn];
int n;
unordered_map<int, int> mp;

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        scanf("%s", s);
        a[0] = 0;
        mp.clear();
        ++mp[0];// 初始时，mp[0]=1
        for(int i = 1;i <= n; ++i) {
            a[i] = a[i-1] + s[i-1] - '0' - 1;
            ++mp[a[i]];
        }
        ll ans = 0;
        for(auto it: mp) {
            ans += 1LL * it.second * (it.second - 1) / 2;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31