题目描述

给你一个二进制字符串 $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 \leq s.length \leq 10^5$

算法

(枚举) $O(n)$

1. 枚举每一段全为$1$的区间
2. 对于一个长为$n$的全$1$区间，仅含$1$的子串数为$\frac{(1 + n) \times n}{2}$
3. 把每一段的个数加起来即为答案
4. $n$可能很大，需要用$long$
5. 最后别忘记求模

时间复杂度

字符串只会被遍历一次

C++ 代码

class Solution {
public:
    int numSub(string s) {
        int n = s.size(), ret = 0, mod = 1e9 + 7;
        for (int i = 0; i < n; i ++ ) {
            if (s[i] == '0') continue;
            int j = i;
            while (j < n && s[j] == '1') j ++ ;
            ret = (ret + (long)(1 + j - i) * (j - i) / 2) % mod;
            i = j - 1;
        }
        return ret;
    }
};