LeetCode 题解工作台
仅含 1 的子串数
给你一个二进制字符串 s （仅由 '0' 和 '1' 组成的字符串）。 返回所有字符都为 1 的子字符串的数目。 由于答案可能很大，请你将它对 10^9 + 7 取模后返回。 示例 1： 输入： s = "0110111" 输出 ：9 解释： 共有 9 个子字符串仅由 '1' 组成 "1" -> 5…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数学·string
答案摘要
我们遍历字符串 ，用一个变量 记录当前连续的 1 的个数，用变量 记录答案。当遍历到字符 时，如果 $s[i] = 0$，则 置 0，否则 自增 1，然后 自增 ，并对 $10^9 + 7$ 取模。 遍历结束，返回 即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·string 题型思路
题目描述
给你一个二进制字符串 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 的个数，用变量 记录答案。当遍历到字符 时，如果 ，则 置 0，否则 自增 1，然后 自增 ，并对 取模。
遍历结束，返回 即可。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
相似题目：
class Solution:
def numSub(self, s: str) -> int:
mod = 10**9 + 7
ans = cur = 0
for c in s:
if c == "0":
cur = 0
else:
cur += 1
ans = (ans + cur) % mod
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because the string is traversed once. Space complexity is O(1) since only counters and the final sum are maintained, independent of string length. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate recognizes the arithmetic series pattern in consecutive 1s.
- question_mark
Watch for correct handling of large results with modulo operations.
- question_mark
Assess whether the candidate optimizes by computing contributions in one pass instead of generating substrings.
常见陷阱
外企场景- error
Attempting to generate all substrings explicitly, which causes timeouts for large strings.
- error
Forgetting to reset the consecutive 1s counter after a 0, leading to incorrect sums.
- error
Neglecting to apply modulo 10^9 + 7, risking overflow for long sequences of 1s.
进阶变体
外企场景- arrow_right_alt
Count substrings with only 0s instead of 1s, requiring minimal code adjustment.
- arrow_right_alt
Calculate substrings of exactly k consecutive 1s, modifying the arithmetic sum approach.
- arrow_right_alt
Extend to 3-character strings and count substrings where all characters are identical.