小苯的子串删除

首先，将数字串s能够分出一个数字数组nums = [a0, a1, a2, a3, ..., an-1]，方便后续计算。

假设nums数组所有元素之和为sum，则sum % 3就代表整个数组多出来的值，只要能够减去这个值，那么剩余的数字就可以是3的倍数（顺便减去一些是3的倍数的区间，那么最终结果也是3的倍数。

从左到右遍历，presum代表[0, i-1]的所有元素的和，同时记录presum % 3出现的次数，假设i = 0时，presum = 0。

我们已经知道sum % 3的值是多少，因此，我们可以在presum中减去这个值。

此时sum - (sum % 3)剩余区间的元素之和的是3的倍数，因此组成的数字是3的倍数。

假设presum - (sum % 3)之后剩余区间叫做presum_remain。

若前面有和presum_remain相同的余数的presum，则也可以算作一种方案。

因此可以删除，余数为0的部分和sum % 3的部分，这也算一种方案。

最终，写出代码：

import sys
from collections import Counter
 
line = sys.stdin.readline().strip().split()
n = int(line[0])
a = sys.stdin.readline().strip()
nums = [0] * n
for i in range(n):
    nums[i] = int(a[i])
 
m_sum = sum(nums)
cnt = Counter()
presum = 0
ans = 0
for i in range(n):
    cnt[presum % 3] += 1
    presum += nums[i]
    ans += cnt[(presum - (m_sum % 3)) % 3]
if m_sum % 3 == 0:
    ans += 1
print(ans)

#include <iostream>
#include <unordered_map>
using namespace std;
int dp[2*100001][3];
int main() {
    int n;
    string s;
    long long ret=0;
    cin >> n >> s;
    int sum=0;
    for(int i=0;i<n;++i){
        sum+=s[i]-'0';
    }
    int left = sum%3;
    dp[0][(s[0]-'0')%3] = 1;
    for(int i =1;i<n;++i){
        switch ((s[i]-'0')%3) {
            case 0:
            dp[i][0] = dp[i-1][0]+1;
            dp[i][1] = dp[i-1][1];
            dp[i][2] = dp[i-1][2];
            break;
            case 1:
            dp[i][0] = dp[i-1][2];
            dp[i][1] = dp[i-1][0]+1;
            dp[i][2] = dp[i-1][1];
            break;
            case 2:
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][2];
            dp[i][2] = dp[i-1][0]+1;
            break;
        }
    }
    for(int i=0;i<n;++i){
        ret+=dp[i][left];
    }
    if(left ==0)
        ret++;
    cout << ret << endl;
    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int sum = 0;
        for(int i = 0;i < n;i ++ ) {
            sum += s.charAt(i) - '0';
        }
        Map<Integer, Integer> cnt = new HashMap<>();
        int presum = 0;long res = 0;
        for(int i = 1;i <= n;i ++ ) {
            cnt.put(presum % 3, cnt.getOrDefault(presum% 3, 0) + 1);
            presum += s.charAt(i - 1) - '0';
            res += cnt.getOrDefault((presum - (sum % 3)) % 3, 0);
        }
        if(sum % 3 == 0) res ++;
        System.out.println(res);
        
    }
}