算法

(数学) $O(n)$

注意到$\sum\limits_{i = l}^r {{a_i}} = r - l + 1 \Leftrightarrow \sum\limits_{i = l}^r {{a_i}} - \sum\limits_{i = l}^r 1 = \sum\limits_{i = l}^r {\left( {{a_i} - 1} \right)} = 0$，于是只需对每个元素$-1$，然后原问题就转化成统计和为$0$的子数组的个数。

C++ 代码

#include <iostream>
#include <vector>
#include <map>
#define int long long

using namespace std;

int n;
string s;

signed main() {
    int t;
    cin >> t;

    while (t--) {
        cin >> n >> s;
        vector<int> v(n);
        for (int i = 0; i < n; ++i) v[i] = s[i] - '0' - 1;

        map<int, int> mp;
        int sum = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            sum += v[i];
            if (sum == 0) ans++;
            ans += mp[sum];
            mp[sum]++;
        }

        cout << ans << '\n';
    }

    return 0;
}