题目描述

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

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

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

样例

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

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

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

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

限制

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

算法

(双指针) $O(n)$

1. 对于每个以 '1' 结尾的位置 $i$，都找到尽可能小的 $j$，满足区间 [j, i] 是连续的 '1'，则当前位置贡献答案 $i - j + 1$。
2. 注意到 $j$ 是随着 $i$ 递增而不减的，所以可以使用双指针。

时间复杂度

• 每个位置最多访问两次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int numSub(string s) {
        const int mod = 1000000007;
        int n = s.size(), ans = 0;

        for (int i = 0, j = 0; i < n; i++) {
            if (s[i] == '1')
                ans = (ans + i - j + 1) % mod;
            else
                j = i + 1;
        }

        return ans;
    }
};