Medium

题目描述

给定一个二进制字符串 s，返回所有字符都为 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'。

提示：

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

解题思路

这道题的核心思想是分组统计连续的 1 的个数。

数学规律分析： 对于一个长度为 n 的连续 1 的区间，其能够形成的子字符串个数为 n * (n + 1) / 2。这是因为：

  • 长度为 1 的子字符串有 n 个
  • 长度为 2 的子字符串有 n-1 个
  • …
  • 长度为 n 的子字符串有 1 个

总计：n + (n-1) + ... + 1 = n * (n + 1) / 2

解法思路：

  1. 遍历字符串，统计每个连续 1 片段的长度
  2. 对于每个长度为 len 的片段，累加 len * (len + 1) / 2 到结果中
  3. 由于答案可能很大，需要对 10^9 + 7 取模

时间复杂度优化： 可以采用双指针或单次遍历的方式，在 O(n) 时间内完成统计。遇到 0 时结算当前连续段的贡献，重新开始计数。

代码实现

class Solution {
public:
    int numSub(string s) {
        const int MOD = 1000000007;
        long long result = 0;
        int count = 0;
        
        for (char c : s) {
            if (c == '1') {
                count++;
            } else {
                if (count > 0) {
                    result = (result + (long long)count * (count + 1) / 2) % MOD;
                    count = 0;
                }
            }
        }
        
        // 处理最后一段连续的1
        if (count > 0) {
            result = (result + (long long)count * (count + 1) / 2) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 10**9 + 7
        result = 0
        count = 0
        
        for c in s:
            if c == '1':
                count += 1
            else:
                if count > 0:
                    result = (result + count * (count + 1) // 2) % MOD
                    count = 0
        
        # 处理最后一段连续的1
        if count > 0:
            result = (result + count * (count + 1) // 2) % MOD
            
        return result

public class Solution {
    public int NumSub(string s) {
        const int MOD = 1000000007;
        long result = 0;
        int count = 0;
        
        foreach (char c in s) {
            if (c == '1') {
                count++;
            } else {
                if (count > 0) {
                    result = (result + (long)count * (count + 1) / 2) % MOD;
                    count = 0;
                }
            }
        }
        
        // 处理最后一段连续的1
        if (count > 0) {
            result = (result + (long)count * (count + 1) / 2) % MOD;
        }
        
        return (int)result;
    }
}

var numSub = function(s) {
    const MOD = 1000000007;
    let result = 0;
    let count = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '1') {
            count++;
        } else {
            result = (result + (count * (count + 1) / 2) % MOD) % MOD;
            count = 0;
        }
    }
    
    result = (result + (count * (count + 1) / 2) % MOD) % MOD;
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

相关题目