LeetCode 2222题解析：高效统计"010"与"101"子序列数量的算法优化
一、题目解读
题目要求计算给定字符串中包含"010"或"101"子序列的数量。关键难点在于高效遍历所有子序列，避免重复计算。传统暴力解法时间复杂度O(n^3)会超时，需借助前缀计数与后缀计数的组合策略，将时间复杂度优化至O(n)，从而满足题目要求。
二、解题思路
核心思想：利用前缀数组与后缀数组记录局部统计信息，通过中间位置遍历实现O(1)查询。
1. 预处理：创建前缀数组记录每个位置左侧"0"与"1"的数量，后缀数组记录右侧"0"与"1"的数量。
2. 遍历中间字符：若当前为"0"，则计算左侧"1"数量×右侧"1"数量（对应"101"）；若为"1"，则计算左侧"0"数量×右侧"0"数量（对应"010"）。
3. 累加所有有效中间位置的结果，避免重复统计。
三、解题步骤
步骤1：初始化前缀与后缀数组
创建4个数组：prefix0（前缀"0"数量）、prefix1（前缀"1"数量）、suffix0（后缀"0"数量）、suffix1（后缀"1"数量）。
初始化首元素：根据首字符是否为"0"或"1"填充对应前缀值。
步骤2：计算前缀计数
从左到右遍历，递推公式：prefix0[i] = prefix0[i-1] + (s[i] == '0')，prefix1[i] = prefix1[i-1] + (s[i] == '1')。
步骤3：计算后缀计数
从右到左遍历，递推公式：suffix0[i] = suffix0[i+1] + (s[i] == '0')，suffix1[i] = suffix1[i+1] + (s[i] == '1')。
步骤4：遍历中间位置统计结果
仅考虑i=1到n-2的位置（中间字符需两侧均有字符）。
若s[i]=='0'，则贡献为prefix1[i-1] * suffix1[i+1]（左侧"1"×右侧"1"）。
若s[i]=='1'，则贡献为prefix0[i-1] * suffix0[i+1]（左侧"0"×右侧"0"）。
步骤5：返回累加结果
最终结果res需使用long long类型避免整数溢出。
四、代码+注释
class Solution {
public:
long long numberOfWays(string s) {
int n = s.size(); // 字符串长度
vector<int> prefix0(n, 0), prefix1(n, 0); // 前缀0/1数量
vector<int> suffix0(n, 0), suffix1(n, 0); // 后缀0/1数量
// 计算前缀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');
prefix1[i] = prefix1[i-1] + (s[i] == '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');
suffix1[i] = suffix1[i+1] + (s[i] == '1');
}
long long res = 0; // 结果需使用long long避免溢出
for (int i = 1; i < n-1; ++i) { // 遍历中间位置
if (s[i] == '0') { // 统计"101"
res += (long long)prefix1[i-1] * suffix1[i+1];
} else { // 统计"010"
res += (long long)prefix0[i-1] * suffix0[i+1];
}
}
return res;
}
};五、总结
本文提供的算法通过前缀和后缀计数的巧妙结合，将子序列统计转化为局部信息的乘积，大幅降低时间复杂度至O(n)，同时利用动态规划思想避免重复计算。代码简洁高效，适用于需要快速处理字符串子序列的场景。该解法不仅满足LeetCode 2222题的要求，也为同类问题提供了优化思路。
原创内容 转载请注明出处
