题意

有一个包含 $\texttt{a}$ 和 $\texttt{b}$ 的字符串 $s$，把其中的 $\texttt{a}$ 替换成 $0$，$\texttt{b}$ 替换成 $1,0$，得到一个 $01$ 序列 $\textit{bits}$。

你需要把 $\textit{bits}$ 还原回字符串 $s$，判断 $s$ 的最后一个字符是不是 $\texttt{a}$。

思路

根据题意，两种字符替换后的第一个数字一定是不同的，一个是 $0$，另一个是 $1$。

换句话说，我们可以通过 $\textit{bits}[0]$ 确定字符串的第一个字符：

• 如果 $\textit{bits}[0]=0$，那么是 $\texttt{a}$，把 $\textit{bits}[0]$ 去掉。
• 如果 $\textit{bits}[0]=1$，那么是 $\texttt{b}$，把 $\textit{bits}[0]$ 和 $\textit{bits}[1]$ 去掉。

重复该过程，直到 $\textit{bits}$ 剩下至多一个数字。

分类讨论：

• 如果最后剩下一个数字，由于题目保证 $\textit{bits}[n-1] = 0$，所以字符串的最后一个字符是 $\texttt{a}$，返回 $\texttt{true}$。
• 如果最后没有剩下数字，说明字符串的最后一个字符是 $\texttt{b}$，返回 $\texttt{false}$。

示例 1 是 $[1,0] + [0]$，满足要求。

示例 2 是 $[1,1] + [1,0]$，不满足要求。

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        n = len(bits)
        i = 0
        while i < n - 1:  # 循环直到剩下至多一个数字
            i += bits[i] + 1  # 如果 bits[i] == 1 则跳过下一位
        return i == n - 1  # 注意题目保证 bits[n-1] == 0，无需判断

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int n = bits.length;
        int i = 0;
        while (i < n - 1) { // 循环直到剩下至多一个数字
            i += bits[i] + 1; // 如果 bits[i] == 1 则跳过下一位
        }
        return i == n - 1; // 注意题目保证 bits[n-1] == 0，无需判断
    }
}

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int n = bits.size();
        int i = 0;
        while (i < n - 1) { // 循环直到剩下至多一个数字
            i += bits[i] + 1; // 如果 bits[i] == 1 则跳过下一位
        }
        return i == n - 1; // 注意题目保证 bits[n-1] == 0，无需判断
    }
};

bool isOneBitCharacter(int* bits, int bitsSize) {
    int i = 0;
    while (i < bitsSize - 1) { // 循环直到剩下至多一个数字
        i += bits[i] + 1; // 如果 bits[i] == 1 则跳过下一位
    }
    return i == bitsSize - 1; // 注意题目保证 bits[n-1] == 0，无需判断
}

func isOneBitCharacter(bits []int) bool {
n := len(bits)
i := 0
for i < n-1 { // 循环直到剩下至多一个数字
i += bits[i] + 1 // 如果 bits[i] == 1 则跳过下一位
}
return i == n-1 // 注意题目保证 bits[n-1] == 0，无需判断
}

var isOneBitCharacter = function(bits) {
    const n = bits.length;
    let i = 0;
    while (i < n - 1) { // 循环直到剩下至多一个数字
        i += bits[i] + 1; // 如果 bits[i] == 1 则跳过下一位
    }
    return i === n - 1; // 注意题目保证 bits[n-1] == 0，无需判断
};

impl Solution {
    pub fn is_one_bit_character(bits: Vec<i32>) -> bool {
        let n = bits.len();
        let mut i = 0;
        while i < n - 1 { // 循环直到剩下至多一个数字
            i += (bits[i] + 1) as usize; // 如果 bits[i] == 1 则跳过下一位
        }
        i == n - 1 // 注意题目保证 bits[n-1] == 0，无需判断
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{bits}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

有两种特殊字符：

• 第一种字符可以用一比特 0 表示
• 第二种字符可以用两比特（10 或 11）表示

给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。

示例 1:

输入: bits = [1, 0, 0]
输出: true
解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。
所以最后一个字符是一比特字符。

示例 2:

输入：bits = [1,1,1,0]
输出：false
解释：唯一的解码方式是将其解析为两比特字符和两比特字符。
所以最后一个字符不是一比特字符。

提示:

• 1 <= bits.length <= 1000
• bits[i] 为 0 或 1

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

有两种字符，一种是 0，一种是10或者11。

给出了一个由这两种字符组成的数组，判断最后一位的数字是否一定是单个的 0．

解题方法

遍历

有两种字符串，一种是 0，一种是 10 或 11。即一种长度是1，一种长度是2.

所以找个指针然后遍历一遍：

• 遇到 0 走一步；
• 遇到 1走两步。
  

题目告诉了数组的最后一个元素一定是 0，所以最后如果恰好到达len-1，说明最后一个数字的长度为 1 ，也就是 0，就满足题意了。

代码如下：

###Java

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int N = bits.length;
        int pos = 0;
        while (pos < N - 1) {
            pos += bits[pos] == 1 ? 2 : 1;
        }
        return pos == N - 1;
    }
}

###Python

class Solution(object):
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        pos = 0
        while pos < len(bits) - 1:
            pos += 2 if bits[pos] == 1 else 1
        return pos == len(bits) - 1

###C++

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        const int N = bits.size();
        int pos = 0;
        while (pos < N - 1) {
            pos += bits[pos] == 1 ? 2 : 1;
        }
        return pos == N - 1;
    }
};

时间复杂度

• 时间复杂度：$O(N)$，其中 $N$ 是数组长度；
• 空间复杂度：$O(1)$。

总结

1. 单指针根据题目要求进行移动，最重要的还是理解题意哇！！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会

模拟

根据题意进行模拟即可，使用 $n$ 代指 bits 的长度，$idx$ 为当前「比特字」的开头，从前往后扫描每个「比特字」，如果最后一个「比特字」的开头为 $n - 1$ 返回 True，否则返回 False。

代码：

###Java

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int n = bits.length, idx = 0;
        while (idx < n - 1) {
            if (bits[idx] == 0) idx++;
            else idx += 2;
        }
        return idx == n - 1;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

加练「滑动窗口/模拟」内容

题太简单？不如来学习热乎的 一道结合众多知识点的滑窗综合题 🎉🎉

• 众多滑动窗口变形题的原题
• 一道经典的滑动窗口笔试高频题
• 更贴合笔试/面试的滑动窗口综合题
• 字符串滑动窗口运用题
• 运用小技巧将问题转化为经典滑动窗口求最值问题

考虑加练如下「模拟」相关内容 🍭🍭🍭

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

方法一：模拟

我们可以遍历数组 $\textit{nums}$，用变量 $j$ 记录上一个 $1$ 的下标，那么当前位置 $i$ 的元素为 $1$ 时，只需要判断 $i - j - 1$ 是否小于 $k$ 即可。如果小于 $k$，则说明存在两个 $1$ 之间的 $0$ 的个数小于 $k$，返回 $\text{false}$；否则，将 $j$ 更新为 $i$，继续遍历数组。

遍历结束后，返回 $\text{true}$。

###python

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        j = -inf
        for i, x in enumerate(nums):
            if x:
                if i - j - 1 < k:
                    return False
                j = i
        return True

###java

class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int j = -(k + 1);
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == 1) {
                if (i - j - 1 < k) {
                    return false;
                }
                j = i;
            }
        }
        return true;
    }
}

###cpp

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int j = -(k + 1);
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 1) {
                if (i - j - 1 < k) {
                    return false;
                }
                j = i;
            }
        }
        return true;
    }
};

###go

func kLengthApart(nums []int, k int) bool {
j := -(k + 1)
for i, x := range nums {
if x == 1 {
if i-j-1 < k {
return false
}
j = i
}
}
return true
}

###ts

function kLengthApart(nums: number[], k: number): boolean {
    let j = -(k + 1);
    for (let i = 0; i < nums.length; ++i) {
        if (nums[i] === 1) {
            if (i - j - 1 < k) {
                return false;
            }
            j = i;
        }
    }
    return true;
}

###rust

impl Solution {
    pub fn k_length_apart(nums: Vec<i32>, k: i32) -> bool {
        let mut j = -(k + 1);
        for (i, &x) in nums.iter().enumerate() {
            if x == 1 {
                if (i as i32) - j - 1 < k {
                    return false;
                }
                j = i as i32;
            }
        }
        true
    }
}

时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,0,0,0,1,0,0,1], k = 2
输出：true
解释：每个 1 都至少相隔 2 个元素。

示例 2：

输入：nums = [1,0,0,1,0,1], k = 2
输出：false
解释：第二个 1 和第三个 1 之间只隔了 1 个元素。

提示：

• 1 <= nums.length <= 105
• 0 <= k <= nums.length
• nums[i] 的值为 0 或 1

如果所有相邻的 $1$ 都至少相隔 $k$ 个元素，那么所有 $1$ 都至少相隔 $k$ 个元素。

所以只需检查相邻的 $1$。

记录上一个 $1$ 的位置 $\textit{last}_1$。

如果 $\textit{nums}[i] = 1$ 且 $i - \textit{last}_1 - 1 < k$，即 $i - \textit{last}_1 \le k$，则不满足要求。

为了兼容 $\textit{nums}$ 的第一个 $1$，可以初始化 $\textit{last}_1 = -k-1$。

###py

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        last1 = -inf
        for i, x in enumerate(nums):
            if x != 1:
                continue
            if i - last1 <= k:
                return False
            last1 = i
        return True

###java

class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int last1 = -k - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 1) {
                continue;
            }
            if (i - last1 <= k) {
                return false;
            }
            last1 = i;
        }
        return true;
    }
}

###cpp

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int last1 = -k - 1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 1) {
                continue;
            }
            if (i - last1 <= k) {
                return false;
            }
            last1 = i;
        }
        return true;
    }
};

###c

bool kLengthApart(int* nums, int numsSize, int k) {
    int last1 = -k - 1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 1) {
            continue;
        }
        if (i - last1 <= k) {
            return false;
        }
        last1 = i;
    }
    return true;
}

###go

func kLengthApart(nums []int, k int) bool {
last1 := -k - 1
for i, x := range nums {
if x != 1 {
continue
}
if i-last1 <= k {
return false
}
last1 = i
}
return true
}

###js

var kLengthApart = function(nums, k) {
    let last1 = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 1) {
            continue;
        }
        if (i - last1 <= k) {
            return false;
        }
        last1 = i;
    }
    return true;
};

###rust

impl Solution {
    pub fn k_length_apart(nums: Vec<i32>, k: i32) -> bool {
        let mut last1 = -k - 1;
        for (i, x) in nums.into_iter().enumerate() {
            if x != 1 {
                continue;
            }
            if i as i32 - last1 <= k {
                return false;
            }
            last1 = i as i32;
        }
        true
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

解题思路

此处撰写解题思路

代码

###python3

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        if 1 not in nums:
            return True

        min_len = n = len(nums)
        start = nums.index(1)
        for idx in range(start+1,n):
            if nums[idx] == 1:
                min_len = min(min_len, idx - start - 1)
                start = idx
                if min_len < k:
                    return False
        return True

class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int count = k;
        for(int i=0; i<nums.length; i++){
            if(nums[i]==1){
                if(count<k)
                    return false;
                count = 0;
            }
            else{
                count++;
            }
        }
        return true;
    }
}

方法一：遍历计数

我们遍历字符串 $s$，用一个变量 $\textit{cur}$ 记录当前连续的 1 的个数，用变量 $\textit{ans}$ 记录答案。当遍历到字符 $s[i]$ 时，如果 $s[i] = 0$，则 $\textit{cur}$ 置 0，否则 $\textit{cur}$ 自增 1，然后 $\textit{ans}$ 自增 $\textit{cur}$，并对 $10^9 + 7$ 取模。

遍历结束，返回 $\textit{ans}$ 即可。

###python

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

###java

class Solution {
    public int numSub(String s) {
        final int mod = 1_000_000_007;
        int ans = 0, cur = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '0') {
                cur = 0;
            } else {
                cur++;
                ans = (ans + cur) % mod;
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int numSub(string s) {
        const int mod = 1e9 + 7;
        int ans = 0, cur = 0;
        for (char c : s) {
            if (c == '0') {
                cur = 0;
            } else {
                cur++;
                ans = (ans + cur) % mod;
            }
        }
        return ans;
    }
};

###go

func numSub(s string) (ans int) {
const mod int = 1e9 + 7
cur := 0
for _, c := range s {
if c == '0' {
cur = 0
} else {
cur++
ans = (ans + cur) % mod
}
}
return
}

###ts

function numSub(s: string): number {
    const mod = 1_000_000_007;
    let [ans, cur] = [0, 0];
    for (const c of s) {
        if (c === '0') {
            cur = 0;
        } else {
            cur++;
            ans = (ans + cur) % mod;
        }
    }
    return ans;
}

###rust

impl Solution {
    pub fn num_sub(s: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut ans: i32 = 0;
        let mut cur: i32 = 0;
        for c in s.chars() {
            if c == '0' {
                cur = 0;
            } else {
                cur += 1;
                ans = (ans + cur) % MOD;
            }
        }
        ans
    }
}

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(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 次

示例 3：

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

示例 4：

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

提示：

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

遍历 $s$ 的过程中，记录上一个 $0$ 的位置 $\textit{last}_0$。

如果 $s[i]=1$，那么对于右端点为 $i$ 的全 $1$ 子串，左端点可以是

$$
\textit{last}_0+1,\textit{last}_0+2,\ldots,i-1,i
$$

一共有 $i - \textit{last}_0$ 个，加到答案中。

比如 $\textit{last}_0=2$，现在 $s[5]=1$，那么子串 $[3,5],[4,5],[5,5]$ 都只包含 $1$，有 $5-2=3$ 个以 $5$ 为右端点的全 $1$ 子串。

可能一开始没有 $0$，为了让公式兼容这种情况，初始化 $\textit{last}_0=-1$。

注意答案不超过 $64$ 位整数的最大值，可以在最后返回时再取模。

###py

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 1_000_000_007
        ans = 0
        last0 = -1
        for i, ch in enumerate(s):
            if ch == '0':
                last0 = i  # 记录上个 0 的位置
            else:
                ans += i - last0  # 右端点为 i 的全 1 子串个数
        return ans % MOD

###java

class Solution {
    public int numSub(String s) {
        final int MOD = 1_000_000_007;
        long ans = 0;
        int last0 = -1;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '0') {
                last0 = i; // 记录上个 0 的位置
            } else {
                ans += i - last0; // 右端点为 i 的全 1 子串个数
            }
        }
        return (int) (ans % MOD);
    }
}

###cpp

class Solution {
public:
    int numSub(string s) {
        constexpr int MOD = 1'000'000'007;
        long long ans = 0;
        int last0 = -1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '0') {
                last0 = i; // 记录上个 0 的位置
            } else {
                ans += i - last0; // 右端点为 i 的全 1 子串个数
            }
        }
        return ans % MOD;
    }
};

###c

#define MOD 1000000007

int numSub(char* s) {
    long long ans = 0;
    int last0 = -1;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '0') {
            last0 = i; // 记录上个 0 的位置
        } else {
            ans += i - last0; // 右端点为 i 的全 1 子串个数
        }
    }
    return ans % MOD;
}

###go

func numSub(s string) (ans int) {
const mod = 1_000_000_007
last0 := -1
for i, ch := range s {
if ch == '0' {
last0 = i // 记录上个 0 的位置
} else {
ans += i - last0 // 右端点为 i 的全 1 子串个数
}
}
return ans % mod
}

###js

var numSub = function(s) {
    const MOD = 1_000_000_007;
    let ans = 0, last0 = -1;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '0') {
            last0 = i; // 记录上个 0 的位置
        } else {
            ans += i - last0; // 右端点为 i 的全 1 子串个数
        }
    }
    return ans % MOD;
};

###rust

impl Solution {
    pub fn num_sub(s: String) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut ans = 0;
        let mut last0 = -1;
        for (i, ch) in s.bytes().enumerate() {
            if ch == b'0' {
                last0 = i as i32; // 记录上个 0 的位置
            } else {
                ans += (i as i32 - last0) as i64; // 右端点为 i 的全 1 子串个数
            }
        }
        (ans % MOD) as _
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

相似题目

2348. 全 0 子数组的数目

专题训练

见下面双指针题单的「六、分组循环」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

###c++

class Solution {
public:
    int numSub(string s) {
        int res = 0, cnt = 0;
        int mod = pow(10,9) + 7;

        for(char c: s){
            if(c=='1'){
                ++cnt;
                res = (res + cnt) % mod;
            } 
            else cnt = 0;
        }

        return res;
    }
};

方法一：遍历字符串寻找最长子串

如果一个所有字符都为 $1$ 的字符串的长度为 $k$，则该字符串包含的所有字符都为 $1$ 的子字符串（包括该字符串本身）的数量是 $\dfrac{k * (k + 1)}{2}$。

首先寻找到所有的只包含字符 $1$ 的最长子字符串。这里的「只包含字符 $1$ 的最长子字符串」的意思是，假设该子字符串的下标范围是 $[i, j]$（包含下标 $i$ 和下标 $j$），其中 $i \le j$，该子字符串中的所有字符都是 $1$，且下标 $i$ 满足 $i$ 位于字符串 $s$ 的最左侧或者下标 $i - 1$ 位置的字符是 $0$，以及下标 $j$ 满足 $j$ 位于字符串 $s$ 的最右侧或者下标 $j + 1$ 位置的字符是 $0$。

寻找到所有的只包含字符 $1$ 的最长子字符串之后，就可以计算所有字符都为 $1$ 的子字符串的数量。

具体做法是，从左到右遍历字符串，如果遇到字符 $1$ 则计算连续字符 $1$ 的数量，如果遇到字符 $0$ 则说明上一个只包含字符 $1$ 的最长子字符串遍历结束，根据最长子字符串的长度计算子字符串的数量，然后将连续字符 $1$ 的数量清零。遍历结束后，如果连续字符 $1$ 的数量大于零，则还有最后一个只包含字符 $1$ 的最长子字符串，因此还需要计算其对应的子字符串的数量。

###Java

class Solution {
    public int numSub(String s) {
        final int MODULO = 1000000007;
        long total = 0;
        int length = s.length();
        long consecutive = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '0') {
                total += consecutive * (consecutive + 1) / 2;
                total %= MODULO;
                consecutive = 0;
            } else {
                consecutive++;
            }
        }
        total += consecutive * (consecutive + 1) / 2;
        total %= MODULO;
        return (int) total;
    }
}

###C++

class Solution {
public:
    static constexpr int P = int(1E9) + 7;
    
    int numSub(string s) {
        int p = 0;
        long long ans = 0;
        while (p < s.size()) {
            if (s[p] == '0') {
                ++p;
                continue;
            }
            int cnt = 0;
            while (p < s.size() && s[p] == '1') {
                ++cnt;
                ++p;
            }
            ans = ans + (1LL + (long long)cnt) * cnt / 2;
            ans = ans % P;
        }
        return ans;
    }
};

###Python

class Solution:
    def numSub(self, s: str) -> int:
        total, consecutive = 0, 0
        length = len(s)
        for i in range(length):
            if s[i] == '0':
                total += consecutive * (consecutive + 1) // 2
                consecutive = 0
            else:
                consecutive += 1
        
        total += consecutive * (consecutive + 1) // 2
        total %= (10**9 + 7)
        return total

###C#

public class Solution {
    public int NumSub(string s) {
        const int MODULO = 1000000007;
        long total = 0;
        long consecutive = 0;
        foreach (char c in s) {
            if (c == '0') {
                total += consecutive * (consecutive + 1) / 2;
                total %= MODULO;
                consecutive = 0;
            } else {
                consecutive++;
            }
        }
        total += consecutive * (consecutive + 1) / 2;
        total %= MODULO;
        return (int)total;
    }
}

###Go

func numSub(s string) int {
    const MODULO = 1000000007
    total := 0
    consecutive := 0
    for _, c := range s {
        if c == '0' {
            total += consecutive * (consecutive + 1) / 2
            total %= MODULO
            consecutive = 0
        } else {
            consecutive++
        }
    }
    total += consecutive * (consecutive + 1) / 2
    total %= MODULO
    return total
}

###C

int numSub(char * s) {
    const int MODULO = 1000000007;
    long total = 0;
    long consecutive = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '0') {
            total += consecutive * (consecutive + 1) / 2;
            total %= MODULO;
            consecutive = 0;
        } else {
            consecutive++;
        }
    }
    total += consecutive * (consecutive + 1) / 2;
    total %= MODULO;
    return (int)total;
}

###JavaScript

var numSub = function(s) {
    const MODULO = 1000000007;
    let total = 0;
    let consecutive = 0;
    for (const c of s) {
        if (c === '0') {
            total += consecutive * (consecutive + 1) / 2;
            total %= MODULO;
            consecutive = 0;
        } else {
            consecutive++;
        }
    }
    total += consecutive * (consecutive + 1) / 2;
    total %= MODULO;
    return total;
};

###TypeScript

function numSub(s: string): number {
    const MODULO = 1000000007;
    let total = 0;
    let consecutive = 0;
    for (const c of s) {
        if (c === '0') {
            total += consecutive * (consecutive + 1) / 2;
            total %= MODULO;
            consecutive = 0;
        } else {
            consecutive++;
        }
    }
    total += consecutive * (consecutive + 1) / 2;
    total %= MODULO;
    return total;
}

###Rust

impl Solution {
    pub fn num_sub(s: String) -> i32 {
        const MODULO: i64 = 1000000007;
        let mut total: i64 = 0;
        let mut consecutive: i64 = 0;
        for c in s.chars() {
            if c == '0' {
                total += consecutive * (consecutive + 1) / 2;
                total %= MODULO;
                consecutive = 0;
            } else {
                consecutive += 1;
            }
        }
        total += consecutive * (consecutive + 1) / 2;
        total %= MODULO;
        total as i32
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串的长度。需要遍历字符串一次。

• 空间复杂度：$O(1)$。只需要维护有限的变量，空间复杂度是常数。

给你一个二进制字符串 s。

请你统计并返回其中 1 显著 的 子字符串 的数量。

如果字符串中 1 的数量 大于或等于 0 的数量的 平方，则认为该字符串是一个 1 显著 的字符串 。

示例 1：

示例 2：

提示：

• 1 <= s.length <= 4 * 104
• s 仅包含字符 '0' 和 '1'。

Problem: 100348. 统计 1 显著的字符串的数量

[TOC]

解题过程

暴力法，逐个判断，用python3肯定过不了，python3实现虽比C++大5-10倍，但python3循环太慢了……
所以我用了C++暴力这道题，871 / 881。
据说Java时限更长，也不太慢，所以我也试了一下，872 / 881。
C++为什么通不过呢？因为时限太短，而且leetcode貌似开了一些检测，慢的出奇。
Java和C++都不行，上numpy，不通过，878 / 881。
所以再引入一个优化，所有0的数量的平方小于等于开头的0的数量，则跳过，通过了，速度甚至接近$O(n\sqrt{n})$的算法。
Wa了三发，终于通过该题。

复杂度

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n)$

Code

###python3

from numpy import *

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        lz, lo = list(accumulate([i == "0" for i in s])), list(accumulate([i == "1" for i in s]))
        z, o = array(lz, int_), array(lo, int_)
        n = len(s)
        res = 0
        for i in range(n):
            if (z[-1]-(0 if i == 0 else lz[i-1]))**2 <= o[i]-(0 if i == 0 else lo[i-1]):
                res += n-i
            else:
                a = z[i:]-(0 if i == 0 else lz[i-1])
                b = o[i:]-(0 if i == 0 else lo[i-1])
                res += sum(a*a <= b)
        return int(res)

###C++

template<typename T>
T::value_type* change(T p){
    using V = T::value_type;
    V *s = new V[p.size()];
    copy(p.begin(), p.end(), s);
    return s;
}

class Solution {
public:
    int numberOfSubstrings(string t) {
        int n = t.size();
        char *s = change(t);
        int res = 0;
        for (int i = 0; i < n; ++i){
            int z = 0, o = 0;
            for (int j = i; j < n; ++j){
                if (s[j] == '0') ++z;
                else ++o;
                res += z*z <= o;
            }
        }
        return res;
    }
};

###Java

class Solution {
    public int numberOfSubstrings(String t) {
        char s[] = t.toCharArray();
        int res = 0;
        for (int i = 0; i < s.length; ++i){
            int z = 0, o = 0;
            for (int j = i; j < s.length; ++j){
                if (s[j] == '0') ++z;
                else ++o;
                res += (z*z <= o?1:0);
            }
        }
        return res;
    }
}

###python3

from numpy import *

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        z, o = array(list(accumulate([i == "0" for i in s])), int_), array(list(accumulate([i == "1" for i in s])), int_)
        n = len(s)
        res = 0
        for i in range(n):
            a = z[i:]-(0 if i == 0 else z[i-1])
            b = o[i:]-(0 if i == 0 else o[i-1])
            res += sum(a*a <= b)
        return int(res)

分析

设 $\textit{cnt}_0$ 为子串中的 $0$ 的个数，$\textit{cnt}_1$ 为子串中的 $1$ 的个数。

根据题意，$1$ 显著子串必须满足

$$
0\le \textit{cnt}_0^2 \le \textit{cnt}_1 \le n
$$

解得

$$
0\le \textit{cnt}_0 \le \sqrt{n}
$$

所以 $1$ 显著子串至多有 $\lfloor \sqrt{n}\rfloor$ 个 $0$。本题 $\lfloor \sqrt{n}\rfloor\le 200$。

核心思路

枚举子串右端点，分别计算：

• 恰好有 $0$ 个 $0$ 的子串有多少个？
• 恰好有 $1$ 个 $0$ 的子串有多少个？
• 恰好有 $2$ 个 $0$ 的子串有多少个？
• ……
• 恰好有 $\lfloor \sqrt{n}\rfloor$ 个 $0$ 的子串有多少个？

记录 $s$ 中的 $0$ 的下标，方便计算子串个数。

详细思路

设子串右端点为 $r$。

设上一个 $0$ 的下标为 $i$。

那么右端点固定为 $r$ 的子串 $[i+1,r],[i+2,r],\ldots,[r,r]$ 都是不包含 $0$ 的，一定是 $1$ 显著子串，这有 $r-i$ 个。

设上上一个 $0$ 的下标为 $j$。

那么子串 $[j+1,r],[j+2,r],\ldots,[i,r]$ 都恰好有 $1$ 个 $0$。

• 如果 $s_r = 1$，那么这些子串都至少有 $1$ 个 $1$，都是 $1$ 显著子串。
• 如果 $s_r = 0$，也就是 $i = r$，那么最右边的 $[i,r]$ 不是 $1$ 显著子串。

这意味着我们还要考虑子串是否有足够的 $1$。

下面考虑更一般的情况。

{:width=600px}

上图用红线/蓝线标记的子串，右端点相同，左端点不同，都恰好有 $2$ 个 $0$。

子串 $1$ 的个数必须 $\ge$ 子串 $0$ 的个数的平方，也就是至少有 $2^2=4$ 个 $1$。上图中的红色子串不满足要求，蓝色子串满足要求。

在包含的 $0$ 的个数不变的前提下，子串左端点越小，$1$ 的个数越多，越满足要求；子串左端点越大，$1$ 的个数越少，越不满足要求。

算出刚好满足要求的那个蓝色子串的左端点（即左端点的最大值），以及更左边的 $0$ 的位置（图中的 $p$，加一得到左端点的最小值），就能算出蓝色子串的个数。

一般地，外层循环枚举子串右端点 $r=0,1,2,\ldots,n-1$，内层循环枚举子串恰好有 $\textit{cnt}_0 = 0,1,2,\ldots$ 个 $0$，如果 $\textit{cnt}_0^2$ 超过了 $[0,r]$ 中的 $1$ 的个数，则跳出枚举 $\textit{cnt}_0$ 的循环。

设当前枚举的 $\textit{cnt}_0$ 对应的左右两个 $0$ 的下标分别为 $p$ 和 $q$。

右端点为 $r$ 且恰好有 $\textit{cnt}_0$ 个 $0$ 的最短子串为 $[q,r]$，设其有 $\textit{cnt}_1$ 个 $1$。

分类讨论：

• 如果 $\textit{cnt}_0^2\le \textit{cnt}_1$，那么子串左端点可以是 $p+1,p+2,\ldots, q$，一共 $q-p$ 个合法左端点。
• 如果 $\textit{cnt}_0^2> \textit{cnt}_1$，那么还需要包含至少 $\textit{cnt}_0^2 - \textit{cnt}_1$ 个 $1$，所以子串左端点的最大值为 $q - (\textit{cnt}_0^2 - \textit{cnt}_1)$，最小值为 $p+1$，一共 $q - (\textit{cnt}_0^2 - \textit{cnt}_1) - p$ 个合法左端点。如果个数是负数，则没有合法左端点。

综合一下，合法左端点最小是 $p+1$，最大是 $q - \max(\textit{cnt}_0^2 - \textit{cnt}_1, 0)$，所以一共有

$$
q - \max(\textit{cnt}_0^2 - \textit{cnt}_1, 0) - p
$$

个合法左端点。考虑到上式可能是负数，所以还要再与 $0$ 取最大值，得

$$
\max\left(q - \max(\textit{cnt}_0^2 - \textit{cnt}_1, 0) - p, 0\right)
$$

累加上式，即为答案。

为了知道 $0$ 的下标，我们用一个列表记录遍历到的 $0$ 的下标。

###py

# 手写 max 更快
max = lambda a, b: b if b > a else a

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        pos0 = [-1]  # 哨兵，方便处理 cnt0 达到最大时的计数
        total1 = 0  # [0,r] 中的 1 的个数
        ans = 0

        for r, ch in enumerate(s):
            if ch == '0':
                pos0.append(r)  # 记录 0 的下标
            else:
                total1 += 1
                ans += r - pos0[-1]  # 单独计算不含 0 的子串个数

            # 倒着遍历 pos0，就相当于在从小到大枚举 cnt0
            for i in range(len(pos0) - 1, 0, -1):
                cnt0 = len(pos0) - i
                if cnt0 * cnt0 > total1:
                    break
                p, q = pos0[i - 1], pos0[i]
                cnt1 = r - q + 1 - cnt0  # [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
                ans += max(q - max(cnt0 * cnt0 - cnt1, 0) - p, 0)

        return ans

###java

class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        int[] pos0 = new int[n + 1]; // 0 的下标
        pos0[0] = -1; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
        int size = 1;
        int total1 = 0; // [0,r] 中的 1 的个数
        int ans = 0;

        for (int r = 0; r < n; r++) {
            if (s.charAt(r) == '0') {
                pos0[size++] = r; // 记录 0 的下标
            } else {
                total1++;
                ans += r - pos0[size - 1]; // 单独计算不含 0 的子串个数
            }

            // 倒着遍历 pos0，那么 cnt0 = size - i
            for (int i = size - 1; i > 0 && (size - i) * (size - i) <= total1; i--) {
                int p = pos0[i - 1];
                int q = pos0[i];
                int cnt0 = size - i;
                int cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
                ans += Math.max(q - Math.max(cnt0 * cnt0 - cnt1, 0) - p, 0);
            }
        }

        return ans;
    }
}

###cpp

class Solution {
public:
    int numberOfSubstrings(string s) {
        vector<int> pos0 = {-1}; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
        int total1 = 0; // [0,r] 中的 1 的个数
        int ans = 0;
        for (int r = 0; r < s.size(); r++) {
            if (s[r] == '0') {
                pos0.push_back(r); // 记录 0 的下标
            } else {
                total1++;
                ans += r - pos0.back(); // 单独计算不含 0 的子串个数
            }

            int m = pos0.size();
            // 倒着遍历 pos0，那么 cnt0 = m - i
            for (int i = m - 1; i > 0 && (m - i) * (m - i) <= total1; i--) {
                int p = pos0[i - 1], q = pos0[i];
                int cnt0 = m - i;
                int cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
                ans += max(q - max(cnt0 * cnt0 - cnt1, 0) - p, 0);
            }
        }
        return ans;
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int numberOfSubstrings(char* s) {
    int n = strlen(s);
    int* pos0 = malloc((n + 1) * sizeof(int)); // 0 的下标
    pos0[0] = -1; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
    int size = 1;
    int total1 = 0; // [0,r] 中的 1 的个数
    int ans = 0;

    for (int r = 0; r < n; r++) {
        if (s[r] == '0') {
            pos0[size++] = r; // 记录 0 的下标
        } else {
            total1++;
            ans += r - pos0[size - 1]; // 单独计算不含 0 的子串个数
        }

        // 倒着遍历 pos0，那么 cnt0 = size - i
        for (int i = size - 1; i > 0 && (size - i) * (size - i) <= total1; i--) {
            int p = pos0[i - 1], q = pos0[i];
            int cnt0 = size - i;
            int cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
            ans += MAX(q - MAX(cnt0 * cnt0 - cnt1, 0) - p, 0);
        }
    }

    free(pos0);
    return ans;
}

###go

func numberOfSubstrings(s string) (ans int) {
pos0 := []int{-1} // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
total1 := 0 // [0,r] 中的 1 的个数
for r, ch := range s {
if ch == '0' {
pos0 = append(pos0, r) // 记录 0 的下标
} else {
total1++
ans += r - pos0[len(pos0)-1] // 单独计算不含 0 的子串个数
}

m := len(pos0)
// 倒着遍历 pos0，那么 cnt0 = m-i
for i := m - 1; i > 0 && (m-i)*(m-i) <= total1; i-- {
p, q := pos0[i-1], pos0[i]
cnt0 := m - i
cnt1 := r - q + 1 - cnt0 // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += max(q-max(cnt0*cnt0-cnt1, 0)-p, 0)
}
}
return
}

###js

var numberOfSubstrings = function(s) {
    const pos0 = [-1]; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
    let total1 = 0; // [0,r] 中的 1 的个数
    let ans = 0;
    for (let r = 0; r < s.length; r++) {
        if (s[r] === '0') {
            pos0.push(r); // 记录 0 的下标
        } else {
            total1++;
            ans += r - pos0[pos0.length - 1]; // 单独计算不含 0 的子串个数
        }

        const m = pos0.length;
        // 倒着遍历 pos0，那么 cnt0 = m - i
        for (let i = m - 1; i > 0 && (m - i) * (m - i) <= total1; i--) {
            const p = pos0[i - 1], q = pos0[i];
            const cnt0 = m - i;
            const cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
            ans += Math.max(q - Math.max(cnt0 * cnt0 - cnt1, 0) - p, 0);
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn number_of_substrings(s: String) -> i32 {
        let mut pos0 = vec![-1]; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
        let mut total1 = 0; // [0,r] 中的 1 的个数
        let mut ans = 0;
        for (r, ch) in s.bytes().enumerate() {
            let r = r as i32;
            if ch == b'0' {
                pos0.push(r); // 记录 0 的下标
            } else {
                total1 += 1;
                ans += r - pos0.last().unwrap(); // 单独计算不含 0 的子串个数
            }

            // 倒着遍历 pos0，就相当于在从小到大枚举 cnt0
            for i in (1..pos0.len()).rev() {
                let cnt0 = (pos0.len() - i) as i32;
                if cnt0 * cnt0 > total1 {
                    break;
                }
                let p = pos0[i - 1];
                let q = pos0[i];
                let cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
                ans += 0.max(q - 0.max(cnt0 * cnt0 - cnt1) - p);
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\sqrt{n})$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

注：使用队列，只保存 $r$ 及其左侧的 $\mathcal{O}(\sqrt{n})$ 个 $0$ 的下标，可以把空间复杂度优化到 $\mathcal{O}(\sqrt{n})$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

解法：枚举

设字符串长度为 $n$，显著子串里 $0$ 的数量一定不超过 $\sqrt{n}$。

因此枚举子串的开头，并枚举后续的每个 $0$，直到 $0$ 的数量超过 $\sqrt{n}$。设当前枚举的子串开头是 $i$，当前枚举的 $0$ 的下标是 $j$，下一个 $0$ 的下标是 $k$。那么下标范围 $(j, k)$ 的元素就全是 $1$。下标范围 $[j, k)$ 里有哪些可以作为显著子串的右端点呢？

首先我们检查一下子串 $s[i..k - 1]$ 是否显著，只有它显著了，下标范围 $[j, k)$ 里才有可能出现显著子串的右端点。设子串 $s[i..k - 1]$ 中，$1$ 的数量比 $0$ 的数量平方多 $c$ 个，那么我们可以把子串右端点从 $(k - 1)$ 往左移至多 $c$ 步，它还能是显著的。不过需要注意的是，右端点左移不能超过 $j$，所以一共有 $\min(c + 1, k - j)$ 个下标可以作为显著子串的右端点。

将枚举过程中的答案加起来即可。一共有 $n$ 个子串开头，且每个子串开头我们都枚举了 $\sqrt{n}$ 个 $0$，所以整体复杂度 $\mathcal{O}(n\sqrt{n})$。

参考代码（c++）

###cpp

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        // 最多枚举几个 0
        int lim = sqrt(n) + 2;

        // 计算下一个 0 的位置
        int nxt[n + 1];
        nxt[n] = n;
        for (int i = n - 1; i >= 0; i--) {
            nxt[i] = nxt[i + 1];
            if (s[i] == '0') nxt[i] = i;
        }

        long long ans = 0;
        // 枚举子串开头
        for (int i = 0; i < n; i++) {
            // 从左到右枚举子串里的 0，直到数量超出限制
            for (int j = i, cnt = (s[i] == '0' ? 1 : 0); j < n && cnt <= lim; j = nxt[j + 1], cnt++) {
                // 求出子串里 1 的数量
                int one = (nxt[j + 1] - i) - cnt;
                // 子串 s[i..nxt[j + 1] - 1] 必须是显著的，这一段里才有可能出现显著子串的右端点
                if (one >= 1LL * cnt * cnt) {
                    // 看看子串右端点最多能左移几步
                    int t = one - cnt * cnt + 1;
                    // 和这一段的长度取 min
                    ans += min(t, nxt[j + 1] - j);
                }
            }
        }
        return ans;
    }
};