给定一个只包含 1 和 0 的字符串，return 个大于 0 的子串的数量

Question

假设S是一个只包含0和1的字符串，我想统计S中0个数小于1个数的非空子串的个数。

使用下面给出的蛮力方法，我们可以得到一个在 O(n^2) 中解决此问题的算法：

moreOnes(s):
count = 0
n = s.len()

for i = 1 to n
    one = 0
    zero = 0
    for j = i to n
        if s[i] == '1'
            one++
        else
            zero++
        
        if one > zero
            count++

return count

但是我们能否有一个算法具有更好的时间复杂度 O(n*logn) 或 O(n)，并且 space 复杂度可以是从 O(1) 到 O(n) 的任何值？

Answer 1

考虑一个数组 A[i]，它包含 1..i 范围内的个数减去 1..i.

范围内的零个数

有了这个数组，现在只需 O(1) 时间就可以通过计算 A[j]-A[i-1] 来计算 i..j 的子串中 1 的数量减去 0 的数量。

对于给定的端点 j，您想要找到所有起点 i<=j 使得 A[j]-A[i-1]>0。同样，您想知道 A[i-1] 中有多少个值小于 A[j]。

这可以通过 Fenwick trees 解决：

遍历 j
在 Fenwick 树中的位置 A[j] 添加 1
从 Fenwick 树中查找累积值，范围可达 A[j]-1 - 这是以 j 结尾并满足所需的属性个大于零的子串的数量。

这将花费 O(n) space 的 Fenwick 树和 O(nlogn) 的时间，因为每次查找都是 O(logn)。

（请注意，A[j] 可能为负，而 Fenwick 树通常处理正数据。您可以通过向 A[j] 添加常量偏移量 n 来解决此问题，这样所有条目都是正的。）

给定一个只包含 1 和 0 的字符串，return 个大于 0 的子串的数量

Given a string which contains only ones and zeros, return the number of substrings with ones more than zeros

algorithm

subset

string-decoding

binary-string