---

1513. 仅含 1 的子串数

• 标签：数学、字符串
• 难度：中等

题目链接

• 1513. 仅含 1 的子串数 - 力扣

题目大意

描述：给定一个二进制字符串 $s$。

要求：返回所有字符都为 $1$ 的子字符串数目。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le s.length \le 10^5$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：一次遍历

1. 核心思想

遍历字符串，统计连续 $1$ 的段的长度。对于长度为 $len$ 的连续 $1$ 段，其包含的全 $1$ 子串数为 $\frac{len \times (len + 1)}{2}$。

2. 具体步骤

第 1 步：$ans = 0$，连续计数 $cnt = 0$。

第 2 步：遍历每个字符：

• 如果是 '1'：$cnt += 1$。
• 如果是 '0'：$ans += cnt \times (cnt + 1) // 2$，$cnt = 0$。

第 3 步：处理末尾的连续 $1$。

第 4 步：返回 $ans \% MOD$。

3. 举例说明

以 $s = "0110111"$ 为例：

• $i=0$：'0'，$cnt=0$。
• $i=1$：'1'，$cnt=1$。
• $i=2$：'1'，$cnt=2$。
• $i=3$：'0'，$ans += 2\times3/2 = 3$，$cnt=0$。
• $i=4$：'1'，$cnt=1$。
• $i=5$：'1'，$cnt=2$。
• $i=6$：'1'，$cnt=3$。
• 结束：$ans += 3\times4/2 = 6$。

$ans = 3 + 6 = 9$。

验证：段 "11"：$2$ 个字符，子串 $"1"$（第 $1$ 个）、$"1"$（第 $2$ 个）、$"11"$ → $3$ 个。
段 "111"：$3$ 个字符，子串 $3+2+1=6$ 个。共 $9$ 个。

思路 1：代码

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        ans = 0
        cnt = 0
        for ch in s:
            if ch == '1':
                cnt += 1
            else:
                ans = (ans + cnt * (cnt + 1) // 2) % MOD
                cnt = 0
        ans = (ans + cnt * (cnt + 1) // 2) % MOD
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。