C. Good Subarrays

You are given an array a1,a2,…,an consisting of integers from 0 to 9. A subarray al,al+1,al+2,…,ar−1,ar is good if the sum of elements of this subarray is equal to the length of this subarray (∑i=lrai=r−l+1).

For example, if a=[1,2,0], then there are 3 good subarrays: a1…1=[1],a2…3=[2,0] and a1…3=[1,2,0].

Calculate the number of good subarrays of the array a.

Input
The first line contains one integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains one integer n (1≤n≤105) — the length of the array a.

The second line of each test case contains a string consisting of n decimal digits, where the i-th digit is equal to the value of ai.

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output
For each test case print one integer — the number of good subarrays of the array a.

Example
inputCopy
3
3
120
5
11011
6
600005
outputCopy
3
6
1
Note
The first test case is considered in the statement.

In the second test case, there are 6 good subarrays: a1…1, a2…2, a1…2, a4…4, a5…5 and a4…5.

In the third test case there is only one good subarray: a2…6.

题意
若子数组的元素之和等于元素个数，那么这个子数组就为好子数组。那么给你一个子数组序列字符串，判断该序列有多少个好子数组。
思路
正常前缀和做法会超时，这题需要优化一下
我们将每一位上的数组-1，就可以把问题转化为求区间和为0的问题
我们需要维护一个前缀和，当我们计算到第i位的时候，假设前缀和为x，如果x为0的话，答案+1，并且如果前面有一段前缀和为0的话，加上前面前缀和为0出现的次数（相减的区间和为0）
如果前缀和不为0，那么我们只需要减去一段区间和为x的区间就可以了（相减的区间和为0）

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
map<LL, LL>mp;
int main()
{
	LL t;
	cin >> t;
	while (t--)
	{
		LL n;
		cin >> n;
		string s;
		cin >> s;
		LL sum = 0,ans=0;
		mp.clear();
		for (LL i = 0; i < n; i++)
		{
			sum += s[i] - '0' - 1;
			if (sum == 0) ans++;
			ans += mp[sum];
			mp[sum]++;
		}
		cout << ans << endl;
	}
}
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
32
33