LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.16
• 题目：1513.仅含1的子串数
• 难度：中等
• 标签: 数学 字符串

1. 题目理解

问题描述：
给你一个二进制字符串 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 次

2. 解题思路

核心观察

连续的 k 个 '1' 可以组成的子串数目为 (k \times (k + 1) / 2)（数学推导：长度为1的子串有k个，长度为2的有k-1个...长度为k的有1个，总和为 (k + (k-1) + ... + 1 = k \times (k + 1) / 2)）。

因此，我们只需遍历字符串，统计每一段连续 '1' 的长度 count，并累加每段对应的子串数即可。

算法步骤

1. 初始化结果 res 为 0，遍历指针 pos 为 0。
2. 遍历字符串，当遇到 '1' 时，统计连续 '1' 的长度 count。
3. 对每段连续 '1'，计算其贡献的子串数 (count \times (count + 1) / 2)，并对 (10^9 + 7) 取模后累加到 res。
4. 最终返回 res 对 (10^9 + 7) 取模的结果。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
 public static int numSub(String s) {
        int res=0;
        int n=s.length();
        int pos=0;
        int mod = 1000000007;
        while(pos<n){
            if(s.charAt(pos)=='1'){
                int count=1;
                while (pos+1<n&&s.charAt(pos+1)=='1'){
                    pos++;
                    count++;
                }
                long temp = (long) count * (count + 1) / 2;
                res = (int) ((res + temp) % mod);
            }
            pos++;
        }
            return res;
    }
}

4. 代码优化说明

• 溢出处理：使用 long 类型存储中间结果 temp，避免 count \times (count + 1) 时的整数溢出（例如当 count 很大时，int 会溢出导致结果错误）。
• 取模时机：每一步计算 temp 后立即对 mod 取模，保证 res 始终在合理范围内，避免最终溢出。

5. 复杂度分析

• 时间复杂度：(O(n))，其中 (n) 是字符串 s 的长度。只需遍历字符串一次，每个字符最多被访问两次（一次在 pos 遍历，一次在 count 统计时）。
• 空间复杂度：(O(1))，仅使用常数级额外空间。

6. 总结

本题的核心是利用数学规律（连续 k 个 '1' 可组成 (k \times (k + 1) / 2) 个子串），将问题转化为统计每段连续 '1' 的长度并累加其贡献。需要注意的是，由于结果可能很大，必须在计算过程中对 (10^9 + 7) 取模，并通过 long 类型避免中间结果溢出，确保最终结果的正确性。