题目

给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例 1：

输入：s = "0110111" 输出：9 解释：共有 9 个子字符串仅由 '1' 组成 "1" -> 5 次 "11" -> 3 次 "111" -> 1 次

示例 2：

输入：s = "101" 输出：2 解释：子字符串 "1" 在 s 中共出现 2 次

示例 3：

输入：s = "111111" 输出：21 解释：每个子字符串都仅由 '1' 组成

示例 4：

输入：s = "000" 输出：0

提示：

• s[i] == '0' 或 s[i] == '1'
• 1 <= s.length <= 10^5

解题思路

1. 观察规律（数学法）

让我们看一段连续的 1，比如 111（长度为 3）：

• 长度为 1 的子串：1, 1, 1 (共 3 个)
• 长度为 2 的子串：11, 11 (共 2 个)
• 长度为 3 的子串：111 (共 1 个)

总数 = 3 + 2 + 1 = 6。

通用的数学规律是：

如果有一段连续的 1，长度为 $N$，那么它包含的全 1 子串总数就是从 1 加到 $N$ 的和，即等差数列求和公式：

$$\text{Total} = \frac{N \times (N + 1)}{2}$$

思路一（分块计算）：

你可以遍历字符串，遇到 0 就把前面统计的 1 的长度结算一次，套用公式，然后清零重新统计。

2. 增量统计法（推荐，代码更简洁）

这是最适合编程实现的思路，也是你之前代码试图实现的方法。

我们不需要等到一段 1 结束了再算总账，而是每遇到一个 '1'，就立刻计算它对答案的贡献。

假设我们遍历到第 i 个位置，且它是连续第 k 个 1：

• 如果是第 1 个 1 (如 ...01)：它贡献了 1 个新子串（就是它自己 "1"）。
• 如果是第 2 个 1 (如 ...011)：它贡献了 2 个新子串（"1" 和 "11"，都以当前这个 1 结尾）。
• 如果是第 3 个 1 (如 ...0111)：它贡献了 3 个新子串（"1", "11", "111"）。

结论：

当前字符如果是 1，且它是连续的第 count 个 1，那么它就给总答案增加了 count 个子串。

具体代码

func numSub(s string) int {

    ans := 0
    circle_count := 0
    for _, char := range s {
        if char == '1' {
            circle_count++
            ans = (ans + circle_count) % (1e9 + 7)
        } else {
                circle_count = 0
        }
    }
    return ans
}