喵~ 主人，今天天气真好，最适合窝在沙发上，一边晒太阳一边解决一道有趣的算法题了，不是吗？今天我们要看的是 Codeforces 上的 1398C - Good Subarrays，一起来看看吧！

题目大意

这道题目是说，我们有一个只包含 0 到 9 数字的数组 a。我们需要找到其中 "好子数组" 的数量，喵~

那什么是“好子数组”呢？一个从下标 l 到 r 的子数组 a[l...r] 如果是“好的”，必须满足一个条件：这个子数组里所有元素的和，恰好等于这个子数组的长度。

用数学公式表达就是： $\sum\limits_{i=l}^{r} a_i = r - l + 1$

举个例子，如果数组是 a = [1, 2, 0]：

• 子数组 [1] (l=1, r=1): 和是 1，长度是 1。1 == 1，所以它是好子数组，喵~
• 子数组 [2, 0] (l=2, r=3): 和是 2+0=2，长度是 3-2+1=2。2 == 2，所以它也是好子数组，喵~
• 子数组 [1, 2, 0] (l=1, r=3): 和是 1+2+0=3，长度是 3-1+1=3。3 == 3，它还是好子数组，喵~ 所以对于 [1, 2, 0]，总共有 3 个好子数组。

我们的任务就是写一个程序，来数出给定数组里到底有多少个这样的好子数组。

解题思路

这个问题看起来有点棘手，但只要我们稍微变个戏法，它就会变得很简单喵~

我们先来看看那个核心条件： $\sum\limits_{i=l}^{r} a_i = r - l + 1$

这个等式两边都有变量，不太好处理。让我们把右边的长度项移到左边来，看看会发生什么奇迹！

$\sum\limits_{i=l}^{r} a_i - (r - l + 1) = 0$

r - l + 1 恰好是这个子数组里元素的个数，也就是 1 的个数。所以我们可以把 (r - l + 1) 写成 Σ1（从 l 到 r 对 1 求和）。

$\sum\limits_{i=l}^{r} a_i - \sum\limits_{i=l}^{r} 1 = 0$

把求和符号合并一下：

$\sum\limits_{i=l}^{r} (a_i - 1) = 0$

看吧！问题一下子就清晰了！我们只需要找到有多少个子数组，其中每个元素都减去 1 之后，新的子数组所有元素的和为 0。

这个问题是不是很眼熟？这正是“和为 0 的子数组”的经典问题呀！解决这个问题，我们的老朋友——前缀和，就要登场啦！

我们定义一个新数组 b，其中 b[i] = a[i] - 1。问题就变成了，计算 b 中有多少个子数组的和为 0。

让 pref[i] 表示数组 b 的前缀和，即 pref[i] = b[1] + b[2] + ... + b[i]。 那么，子数组 b[l...r] 的和就可以表示为 pref[r] - pref[l-1]。

我们需要 pref[r] - pref[l-1] = 0，也就是说，我们只需要找到所有满足 pref[r] = pref[l-1] 的下标对 (l-1, r) 就好了喵！

具体要怎么做呢？ 我们可以用一个哈希表（在 C++ 中就是 std::map 或 std::unordered_map）来记录每个前缀和值出现过的次数。

算法步骤如下：

1. 创建一个 map<int, int> freq 来存储前缀和以及它出现的次数。
2. 初始化一个变量 current_sum = 0 表示当前的前缀和，一个变量 count = 0 来累计好子数组的数量。
3. 在开始遍历之前，先在 freq 中放入 freq[0] = 1。这是个非常重要的小细节哦！它代表一个长度为 0 的“空前缀”，和为 0。这样我们才能正确地统计那些从数组开头就是好子数组的情况（即 pref[r] = 0 的情况）。
4. 从左到右遍历数组 a 的每一个元素 a[i]： a. 计算 b[i] = a[i] - 1。 b. 更新当前前缀和 current_sum += b[i]。 c. 在把 current_sum 记录到哈希表之前，我们先查一下，这个 current_sum 以前出现过多少次？假设是 k 次（k = freq[current_sum]）。这意味着，我们找到了 k 个新的好子数组，它们都以当前位置 i 为右端点。所以，我们让 count += k。 d. 然后，把当前的前缀和也记录下来，让 freq[current_sum] 的计数值加一。
5. 遍历结束后，count 的值就是我们想要的答案啦！

是不是很简单喵？通过一个巧妙的转换和经典的前缀和技巧，问题就迎刃而解了。

题解代码

这是 C++ 的实现代码，加了一些注释方便主人理解哦~

#include <iostream>
#include <string>
#include <vector>
#include <map>

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 喵~ 我们把问题转化一下：
    // a[l...r] 的和等于 r-l+1  <=>  (a[l]-1) + ... + (a[r]-1) 的和等于 0
    // 于是问题就变成了找新数组 b[i] = a[i]-1 中，和为 0 的子数组有多少个。
    // 这可以用前缀和 + 哈希表来解决喵！

    // 用一个 map 来记录前缀和出现的次数。键是前缀和的值，值是它出现的次数。
    std::map<int, int> freq;

    // 初始化 freq[0] = 1，这是为了处理从头开始的子数组 (l=1) 的情况。
    // 因为子数组 b[1...r] 的和是 pref[r]，我们需要 pref[r] = pref[0]。
    // 我们定义 pref[0] = 0，所以这里要预先给和为 0 的前缀和计数为 1。
    freq[0] = 1;

    long long count = 0;
    int current_sum = 0;

    for (char c : s) {
        int digit = c - '0';
        current_sum += (digit - 1);

        // 如果当前的前缀和 `current_sum` 在之前出现过 k 次，
        // 那么就意味着有 k 个起始点可以和当前点配对，形成和为 0 的子数组。
        // map[key] 在 key 不存在时会返回 0，所以可以直接加，很方便喵~
        count += freq[current_sum];

        // 把当前的前缀和也加到 map 里去，为后面的计算做准备。
        freq[current_sum]++;
    }

    std::cout << count << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得快一点喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题主要用到了几个非常核心的算法知识点，掌握了它们，很多问题都会变得容易起来喵！

1. 前缀和 (Prefix Sum)

• 是什么：前缀和是一种预处理技术。对于一个数组 A，它的前缀和数组 P 的定义是 P[i] = A[1] + A[2] + ... + A[i]。
• 有什么用：它最大的用处就是可以在 O(1) 的时间复杂度内计算出原数组任意一个子数组的和。子数组 A[l...r] 的和就等于 P[r] - P[l-1]。
• 在本题的应用：我们利用前缀和将“求子数组的和”这个操作变得高效，从而可以专注于寻找和为特定值的子数组。

2. 哈希表 (Hash Table)

• 是什么：哈希表是一种数据结构，它能提供快速的插入、删除和查找操作。它通过一个“哈希函数”将键（Key）映射到一个桶（Bucket）中，从而实现高效访问。在 C++ 中，std::map（基于红黑树，O(logN)）和 std::unordered_map（基于哈希表，平均 O(1)）都是它的实现。
• 有什么用：它非常适合用来“计数”或者“检查存在性”。
• 在本题的应用：我们用哈希表来存储每个前缀和值出现过的次数。每当我们算出一个新的前缀和，就可以立刻查询到这个值在之前出现过几次，从而快速统计出新增的满足条件的子数组数量。

3. 问题转换 (Problem Transformation)

• 是什么：这是算法竞赛中一种非常重要的思维方式。它指的是将一个看似复杂或陌生的问题，通过数学变换、模型转换等方式，变成一个我们熟悉并且有标准解法的经典问题。
• 在本题的应用：我们将原始条件 Σa[i] = r - l + 1 巧妙地转换成了 Σ(a[i] - 1) = 0。这个转换是解题的关键，它直接将问题引导到了我们熟悉的前缀和领域。所以，当主人遇到难题时，不妨多想一想，能不能给问题化个妆，让它变成我们认识的样子呢，喵~

好啦，今天的讲解就到这里啦！希望主人有所收获。下次再一起玩耍吧，喵~