查找二进制字符串中子序列的出现（非必然连续）

Question

给定一个包含 0 和 1 的二进制字符串。我想知道给定输入字符串中子序列

01

和

10

出现的次数。子序列不一定是连续的。

例如：

input : "10101"
"01" subsequences: 3, with indices (1,2), (1,4), (3,4)
"10" subsequences: 3, with indices (0,1), (0,3), (2,3)

Result = 3 + 3 = 6

我的想法是使用嵌套循环来查找输入字符串中 01 的出现，然后再次使用另一个嵌套循环来获取 10

如何通过降低时间复杂度以最佳方式做到这一点。

Answer 1

我发布了我想到的第一个解决方案，它非常简单干净，我没有考虑2个不同的计数器，但只需稍加修改就可以做到。这个例子严格适用于你的情况，如果你想改变要检查的二进制字符串，这个解决方案将不再合适。

    String word = "10101";
    int result = 0, count0 = 0, count1 = 0;

    for(int i = 0; i < word.length(); i++) {
        if (word.charAt(i) == '0') {
            count0++;
            result += count1;
        }
        else {
            count1++;
            result += count0;
        }

    }
    System.out.println("Count: " + result);