2025-03-14：统计 1 显著的字符串的数量。用go语言，给定一个二进制字符串 s，请你计算其中被称为“1 显著”的子字符串的数量。

一个子字符串被视为“1 显著”，当它包含的 1 的数量大于或等于 0 的数量的平方。

1 <= s.length <= 40000。

s 仅包含字符 ‘0’ 和 ‘1’。

输入：s = “101101”。

输出：16。

解释：

1 不显著的子字符串如下表所示。

总共有 21 个子字符串，其中 5 个是 1 不显著字符串，因此有 16 个 1 显著子字符串。

答案2025-03-13：

题目来自leetcode3234。

大体步骤如下：

1.初始化变量tot1和切片a，切片a中包含了-1作为哨兵，用于记录’0’字符的位置。

2.遍历输入二进制字符串s，对于每个字符：

• 如果当前字符为’0’，将其位置添加到切片a中。

• 如果当前字符为’1’，则计算"1 显著"的子字符串数量(ans)。

• 针对切片a中的不同组合计算额外的"1 显著"子字符串数量，并将计算结果累加到ans中。

3.返回ans作为结果。

总体时间复杂度:

• 代码中的主要循环是遍历输入字符串s，时间复杂度为O(n)，其中n是输入字符串的长度。

总体空间复杂度:

• 额外空间主要用于存储切片a，其最大长度为输入字符串s的长度n，因此额外空间复杂度为O(n)。

在整个过程中，代码根据字符’0’和’1’的分布来计算"1 显著"的子字符串的数量，具体的实现方式是通过维护一个辅助数组a来记录’0’字符的位置，然后根据条件计算"1 显著"的子字符串数量。

Go完整代码如下：

package main

import (
	"fmt"
)

func numberOfSubstrings(s string) (ans int) {
	tot1 := 0
	a := []int{-1} // 哨兵
	for right, b := range s {
		if b == '0' {
			a = append(a, right)
		} else {
			ans += right - a[len(a)-1]
			tot1++
		}
		for k := len(a) - 1; k > 0 && (len(a)-k)*(len(a)-k) <= tot1; k-- {
			cnt0 := len(a) - k
			cnt1 := right - a[k] + 1 - cnt0
			ans += max(a[k]-a[k-1]-max(cnt0*cnt0-cnt1, 0), 0)
		}
	}
	return
}

func main() {
	s := "101101"
	result := numberOfSubstrings(s)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def number_of_substrings(s: str) -> int:
    ans = 0
    tot1 = 0
    a = [-1]  # 哨兵
    for right, b in enumerate(s):
        if b == '0':
            a.append(right)
        else:
            ans += right - a[-1]
            tot1 += 1

        for k in range(len(a) - 1, 0, -1):
            if (len(a) - k) * (len(a) - k) > tot1:
                break
            cnt0 = len(a) - k
            cnt1 = right - a[k] + 1 - cnt0
            ans += max(a[k] - a[k - 1] - max(cnt0 * cnt0 - cnt1, 0), 0)

    return ans

if __name__ == "__main__":
    s = "101101"
    result = number_of_substrings(s)
    print(result)