1513. 仅含 1 的子串数#

题目描述#

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

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

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

示例 1：

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

示例 2：

1
输入：s = "101"
2
输出：2

提示：

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

解题思路#

核心思想#

把字符串按连续的 '1' 分成若干段（用分组循环）。对任意一段长度为 k 的连续 '1'，它内部能形成的全 1 子串数量为：

1
长度为 1 的有 k 个
2
长度为 2 的有 k-1 个
3
...
4
长度为 k 的有 1 个
5
合计 = 1 + 2 + ... + k = k * (k + 1) / 2

把每一段的贡献累加并对 10^9+7 取模即可。因为不同段之间被 '0' 隔开，子串不能跨界，所以互不影响，直接相加。

段贡献示意（s = “0110111”）：

1
"01 1 0 1 1 1"
2
     段1(k=2)       段2(k=3)
3
贡献= 2*3/2=3    贡献= 3*4/2=6
4
总计 = 3 + 6 = 9

算法步骤#

初始化 ans = 0，i = 0。
当 i < n 时：
- 若 s[i] == '0'，i++ 跳过；
- 否则 j = i，内层 while 扩展连续 '1'；段长 k = j - i + 1；
- ans += k*(k+1)//2，i = j + 1。
返回 ans % (10^9+7)。

逐步举例#

以 s = "0110111"，按段统计：

段	区间	长度 k	贡献 k(k+1)/2
1（跳过 ‘0’）	-	-	-
11	[1,2]	2	3
0	-	-	-
111	[4,6]	3	6

合计 3 + 6 = 9。

复杂度分析#

时间复杂度：O(N)，单次线性扫描。
空间复杂度：O(1)。

代码实现#

1
class Solution:
2
    def numSub(self, s: str) -> int:
3
        MOD = 10 ** 9 + 7
4
        ans = 0
5
        n = len(s)
6
        i = 0
7
        while i < n:
8
            if s[i] == '0':
9
                i += 1
10
                continue
11
            j = i
12
            while j + 1 < n and s[j + 1] == '1':
13
                j += 1
14
            k = j - i + 1
15
            ans = (ans + k * (k + 1) // 2) % MOD
16
            i = j + 1
17
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_example1(self):
12
        self.assertEqual(Solution().numSub("0110111"), 9)
13

14
    def test_example2(self):
15
        self.assertEqual(Solution().numSub("101"), 2)
16

17

18
if __name__ == '__main__':
19
    unittest.main()