如何优化二进制字符串中非连续子序列01与10的计数算法时间复杂度

问题描述 #

给定仅由0和1组成的二进制字符串，需要统计其中所有非连续子序列"01"和"10"的出现次数之和。
示例：
输入："10101"

• "01"子序列：3个（对应索引对(1,2)、(1,4)、(3,4)）
• "10"子序列：3个（对应索引对(0,1)、(0,3)、(2,3)）
  结果：3 + 3 = 6

原有实现的问题 #

当前提供的嵌套循环实现时间复杂度为O(n²)，当字符串长度较大时，执行效率会显著下降。

最优优化思路 #

我们可以通过一次遍历完成统计，将时间复杂度降至O(n)，空间复杂度保持O(1)：

• 统计"01"子序列：遍历字符串时，记录当前已出现的'0'的数量。每遇到一个'1'，这个'1'能和之前所有的'0'组成新的"01"子序列，直接把当前'0'的计数加到"01"的总次数中。
• 统计"10"子序列：同理，记录当前已出现的'1'的数量，每遇到一个'0'，就把当前'1'的计数加到"10"的总次数中。
• 最终结果为两者的和。

优化后的Java代码 #

public static int solve(String s) {
    int count01 = 0;
    int count10 = 0;
    int zeroCount = 0;
    int oneCount = 0;
    
    for (char c : s.toCharArray()) {
        if (c == '0') {
            zeroCount++;
            // 当前0可以和前面所有的1组成"10"子序列
            count10 += oneCount;
        } else {
            oneCount++;
            // 当前1可以和前面所有的0组成"01"子序列
            count01 += zeroCount;
        }
    }
    
    return count01 + count10;
}

验证示例 #

以输入"10101"为例：
遍历过程中：

• 第1个字符'1'：oneCount=1，count01 += 0 → count01=0
• 第2个字符'0'：zeroCount=1，count10 +=1 → count10=1
• 第3个字符'1'：oneCount=2，count01 +=1 → count01=1
• 第4个字符'0'：zeroCount=2，count10 +=2 → count10=3
• 第5个字符'1'：oneCount=3，count01 +=2 → count01=3
  最终总和3+3=6，和示例结果一致。

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