三重循环子序列计数超时，如何优化为线性时间复杂度？

你的三重循环实现时间复杂度为O(n³)，当字符串长度较大时必然会超时。我们可以通过一次线性遍历字符串，维护三个计数器的方式将复杂度降至O(n)，具体思路如下：

• 用count1记录遍历到当前位置时，字符c1的出现次数；
• 用count12记录遍历到当前位置时，c1后跟c2的有效组合数量；
• 用count123记录最终需要统计的c1c2c3三元组数量；

遍历字符串的每个字符时，根据当前字符类型更新对应计数器：

1. 如果当前字符是c3，所有已存在的c1c2组合都能和它形成有效三元组，因此count123 += count12；
2. 如果当前字符是c2，所有已存在的c1都能和它形成新的c1c2组合，因此count12 += count1；
3. 如果当前字符是c1，直接增加count1的计数；

这种方式仅需一次线性遍历，完全避免了嵌套循环带来的高复杂度。

优化后的C++代码如下：

#include <iostream>
#include <string>

using namespace std;

int numberSubsequences(const string &s, char c1, char c2, char c3) {
    long long count1 = 0, count12 = 0, count123 = 0;
    // 使用long long避免长字符串场景下的计数溢出
    for (char ch : s) {
        if (ch == c3) {
            count123 += count12;
        } else if (ch == c2) {
            count12 += count1;
        } else if (ch == c1) {
            count1++;
        }
    }
    return static_cast<int>(count123);
}

// 测试示例
int main() {
    string s = "abcabc";
    cout << numberSubsequences(s, 'a', 'b', 'c') << endl; // 输出4
    return 0;
}

内容的提问来源于stack exchange，提问作者serialexperimentshaku