力扣2222题终极攻略：前缀和与后缀和在字符串模式统计中的惊艳应用 | 算法新手必看

一、问题理解与算法思路

题目要求统计二进制字符串中"010"或"101"模式的出现次数。核心思路是通过预处理前缀和后缀数组，避免暴力枚举带来的高时间复杂度。

关键算法步骤：

1. 预处理前缀0和1的数量

2. 预处理后缀0和1的数量

3. 遍历中间位置计算有效组合数

二、完整代码实现（带详细注释）

class Solution { 
public: 
    long long numberOfWays(string s) { 
        int n = s.size(); 
        // 定义前缀数组和后缀数组 
        vector prefix0(n, 0), prefix1(n, 0); 
        vector suffix0(n, 0), suffix1(n, 0);
        // 计算前缀0和1的数量
        prefix0[0] = (s[0] == '0'); // 初始化第一个字符
        prefix1[0] = (s[0] == '1');
        for (int i = 1; i < n; ++i) {
            prefix0[i] = prefix0[i-1] + (s[i] == '0'); // 累加0的个数
            prefix1[i] = prefix1[i-1] + (s[i] == '1'); // 累加1的个数
        }
    
        // 计算后缀0和1的数量
        suffix0[n-1] = (s[n-1] == '0'); // 初始化最后一个字符
        suffix1[n-1] = (s[n-1] == '1');
        for (int i = n-2; i >= 0; --i) {
            suffix0[i] = suffix0[i+1] + (s[i] == '0'); // 反向累加0的个数
            suffix1[i] = suffix1[i+1] + (s[i] == '1'); // 反向累加1的个数
        }
    
        long long res = 0;
        // 遍历每个中间位置
        for (int i = 1; i < n-1; ++i) {
            if (s[i] == '0') {
                // 计算101模式：左边1的数量 × 右边1的数量
                res += (long long)prefix1[i-1] * suffix1[i+1];
            } else {
                // 计算010模式：左边0的数量 × 右边0的数量
                res += (long long)prefix0[i-1] * suffix0[i+1];
            }
        }
    
        return res;
    }
};

三、算法核心解析

1. 前缀数组：记录到当前位置为止0和1的累计数量

2. 后缀数组：记录从当前位置到末尾0和1的累计数量

3. 组合计算：利用前缀后缀数组快速计算可能组合数

四、复杂度分析与优化

1. 时间复杂度：O(n)，只需三次线性遍历

2. 空间复杂度：O(n)，使用四个辅助数组

3. 优化建议：可进一步优化为使用单个变量代替后缀数组

五、常见问题解答

Q：为什么需要同时计算前缀和后缀？ A：前缀帮助我们快速获取左侧信息，后缀帮助我们快速获取右侧信息。

Q：如何处理特殊边界情况？ A：代码已自动处理边界，如首尾字符不会作为中间位置。

Q：算法是否可以处理更长模式？ A：当前算法针对3字符模式，更长模式需要调整算法结构。