夏老师有一个包含 n 个正整数的数组 a ，他想知道数组 a 中有多少个子段的和是3的倍数。 数组的子段为数组中单个或若干个连续的元素，如序列 [1]，[2,3]，[2,3,4] 均为数组 [1,2,3,4,5] 的子段。 当且仅当两个子段的起止下标不同时，两个子段为不同的子段。 输入数据 第一行一个整数n 。 第二行n 个整数，用单个空格隔开，表示数组a 中的各个元素。 输出数据 一个整数，数组 a 中有多少个子段的和是3的倍数。代码实现

这里给出一个时间复杂度为 O(n) 的算法，使用前缀和和哈希表来解决。

具体做法如下：

1. 定义一个哈希表 map，用来保存余数为 0、1、2 的前缀和的个数。初始化时，map[0] = 1，表示前缀和为 0 的个数为 1。

2. 从左到右遍历数组 a，对于每一个位置 i，计算前 i 个元素的前缀和 prefixSum，即 prefixSum = (prefixSum + a[i]) % 3。

3. 如果 map 中已经存在 prefixSum 的值，则将 count 加上对应的值，表示在当前位置下标 i 的子数组中存在多少个子段的和为 3 的倍数。

4. 然后将 prefixSum 的值在 map 中对应的计数器加 1。

5. 最后返回 count 的值即可。

以下是代码实现：

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<int, int> mp;
    mp[0] = 1;  // 前缀和为 0 的个数为 1
    int prefixSum = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        prefixSum = (prefixSum + a[i]) % 3;
        if (mp.find(prefixSum) != mp.end()) {
            count += mp[prefixSum];
        }
        mp[prefixSum]++;
    }
    cout << count << endl;

    return 0;
}