Good Subarrays(前缀和)_综合

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

思路：每个数都减去1，问题转化为，求有有多少个连续子区间，满足 $\sum_{i=l}^{r}==0$ ，只需求出每个前缀和，如果 $sum_{i=1}^l == sum_{i=1}^r$ ，说明 $sum_{i=l+1}^{r} == 0$ 。因此，找出所有前缀和相同的个数x，那么这些前缀和贡献的区间数为 $x*(x-1)/2$ ，注意，初始时， $num_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]=1for(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;
}