线性动态规划：统计二进制子串中0和1数量相等的子串个数
字数 7620 2025-12-16 03:42:12

线性动态规划：统计二进制子串中0和1数量相等的子串个数

问题描述

给定一个二进制字符串 s，它仅由字符 '0' 和 '1' 组成。要求统计并返回其中“0 和 1 数量相等”的非空连续子串的个数。

示例 1：
输入：s = "00110011"
输出：6
解释：满足条件的子串有：

  • "0011" (子串 [0,3])
  • "01" (子串 [1,2])
  • "1100" (子串 [2,5])
  • "10" (子串 [3,4])
  • "0011" (子串 [4,7])
  • "01" (子串 [5,6])

示例 2：
输入：s = "10101"
输出：4
解释：满足条件的子串有：

  • "10" (子串 [0,1])
  • "01" (子串 [1,2])
  • "10" (子串 [2,3])
  • "01" (子串 [3,4])

注意：子串必须是连续的一段字符。

解题思路

这是一个计数问题，要求找出所有满足“0 和 1 数量相等”的连续子串。
我们可以将其转化为“前缀和”的思想，但这里 0 和 1 的数量要相等，而不是和为零。
一个巧妙的转换是：将字符 '0' 视为 -1，将 '1' 视为 1。这样，一个子串中 0 和 1 数量相等，就等价于这个子串的“和”为 0。

于是，问题变成了：在转换后的数组中，找出所有和为 0 的连续子数组的个数。
这可以通过动态规划配合哈希表来高效求解，其核心是“前缀和 + 哈希计数”。

详细步骤

步骤 1：问题转换

  • 定义一个整数数组 arr，长度与字符串 s 相同。
  • 遍历字符串 s，如果 s[i] == '0'，则 arr[i] = -1；如果 s[i] == '1'，则 arr[i] = 1。

转换后的问题：在数组 arr 中，统计和为 0 的连续子数组的个数。

步骤 2：前缀和的定义

  • 定义前缀和 prefixSum[i] 表示从 arr[0] 到 arr[i] 的元素之和（包括两端）。
  • 即 prefixSum[i] = arr[0] + arr[1] + ... + arr[i]。
  • 特别地，定义 prefixSum[-1] = 0，表示在开始之前的前缀和为 0。

关键观察：
对于任意子数组 arr[j...i]（从索引 j 到 i，包含两端），其和为：

sum(arr[j...i]) = prefixSum[i] - prefixSum[j-1]

当这个和为 0 时，有 prefixSum[i] = prefixSum[j-1]。

结论：
满足条件的子数组，其结束位置 i 对应的前缀和，等于某个更早位置（j-1）的前缀和。
所以，我们需要统计，对于每个结束位置 i，有多少个开始位置 j（j ≤ i），使得 prefixSum[j-1] 等于 prefixSum[i]。

步骤 3：动态规划（哈希表计数）

我们可以一边计算前缀和，一边用哈希表记录之前出现过的各个前缀和值的次数。

算法流程：

  1. 初始化哈希表 countMap，键为前缀和的值，值为该前缀和出现的次数。初始时，countMap[0] = 1，表示前缀和为 0 在索引 -1 时出现了一次。
  2. 初始化 currentSum = 0，表示当前的前缀和。
  3. 初始化 result = 0，用于累计满足条件的子串个数。
  4. 遍历字符串 s 的每个字符：
    • 如果当前字符是 '0'，则 currentSum -= 1。
    • 如果当前字符是 '1'，则 currentSum += 1。
    • 检查 currentSum 是否已经在 countMap 中出现过：
      • 如果出现过，说明存在若干个开始位置，使得从那个位置到当前位置的子串和为 0。这些开始位置的个数，就是 countMap[currentSum] 的值。将它们加到 result 中。
    • 将当前 currentSum 的出现次数加 1，更新 countMap。
  5. 遍历结束后，result 即为所求。

原理：
哈希表 countMap 记录了在遍历过程中，每个前缀和值出现了多少次。当我们计算到位置 i 时，currentSum 是 prefixSum[i]。如果之前某个位置 j-1 也有相同的前缀和，那么子串 arr[j...i] 的和就是 0。而 countMap[currentSum] 就记录了这样的 j-1 的个数（即开始位置的选择数）。

步骤 4：示例推导

以 s = "00110011" 为例：

索引 i 字符 currentSum 变化 currentSum 值 countMap 当前状态（前缀和 -> 出现次数） 新增满足条件的子串个数
初始化 0 {0:1} 0
0 '0' -1 -1 {0:1, -1:1} 0
1 '0' -1 -2 {0:1, -1:1, -2:1} 0
2 '1' +1 -1 {0:1, -1:2, -2:1} 1 (因为 -1 出现过 1 次，对应子串 s[1..2]="01")
3 '1' +1 0 {0:2, -1:2, -2:1} 2 (因为 0 出现过 1 次，对应子串 s[0..3]="0011")
4 '0' -1 -1 {0:2, -1:3, -2:1} 3 (因为 -1 出现过 2 次，对应子串 s[2..4]="110" 和 s[1..4]="0110"，但注意："110" 中 0 和 1 数量不等？这里需要验证)

等一下，这里出现了问题！让我们仔细分析。

验证：
当 i=4 时，currentSum = -1，之前出现过 2 次（在 i=0 和 i=2）。

  • 从 j-1 = 0 到 i=4，对应子串 s[1..4] = "0110"（0:2个, 1:2个），确实满足条件。
  • 从 j-1 = 2 到 i=4，对应子串 s[3..4] = "10"（0:1个, 1:1个），也满足条件。

所以 i=4 时新增 2 个，总共 1+2+2=5 个？但示例答案是 6。继续推导：

索引 i 字符 currentSum 值 countMap 更新前 新增个数 累计 result 具体新增的子串（结束于 i）
5 '0' -2 {0:2, -1:3, -2:1} 1 (因为 -2 出现过 1 次) 6 s[2..5]="1100" (0:2,1:2)
6 '1' -1 {0:2, -1:3, -2:2} 3 (因为 -1 出现过 3 次) 9 s[3..6]="1001"? 不，应该检查：j-1 对应前缀和为 -1 的位置有 i=0,2,4。子串分别为 s[1..6]="011001"（不等）, s[3..6]="1001"（不等）, s[5..6]="01"（等）。所以只有最后一个满足。所以这里计算有误。

发现我们多算了！因为我们需要子串中 0 和 1 的数量相等，对应转换后数组的和为 0。但我们的方法统计的是“前缀和相等”的情况，这确实对应和为 0 的子串，但必须确保子串长度至少为 2（因为单个字符不可能相等）。上面的推导中，有一些子串其实不满足数量相等，比如 "110"（0:1,1:2）并不相等，为什么会被计入？

仔细检查：
转换数组：s="00110011" -> arr = [-1, -1, 1, 1, -1, -1, 1, 1]
前缀和：
i=-1: 0
i=0: -1
i=1: -2
i=2: -1
i=3: 0
i=4: -1
i=5: -2
i=6: -1
i=7: 0

查找和为 0 的子串：

  • prefixSum[3] = 0，与 prefixSum[-1]=0 相等 → 子串 s[0..3]="0011"（长度4，0:2,1:2）✔
  • prefixSum[7] = 0，与 prefixSum[-1]=0 相等 → 子串 s[0..7]="00110011"（长度8，0:4,1:4）✔
  • prefixSum[7] = 0，与 prefixSum[3]=0 相等 → 子串 s[4..7]="0011"（长度4，0:2,1:2）✔
  • prefixSum[2] = -1，与 prefixSum[0]=-1 相等 → 子串 s[1..2]="01"（长度2，0:1,1:1）✔
  • prefixSum[4] = -1，与 prefixSum[0]=-1 相等 → 子串 s[1..4]="0110"（长度4，0:2,1:2）✔
  • prefixSum[4] = -1，与 prefixSum[2]=-1 相等 → 子串 s[3..4]="10"（长度2，0:1,1:1）✔
  • prefixSum[6] = -1，与 prefixSum[0]=-1 相等 → 子串 s[1..6]="011001"（长度6，0:3,1:3）✔
  • prefixSum[6] = -1，与 prefixSum[2]=-1 相等 → 子串 s[3..6]="1001"（长度4，0:2,1:2）✔
  • prefixSum[6] = -1，与 prefixSum[4]=-1 相等 → 子串 s[5..6]="01"（长度2，0:1,1:1）✔

我们找到了 9 个子串，但示例说只有 6 个。为什么？

问题在于：示例中只统计“连续的 0 和连续的 1 的组交替出现，且相邻两组 0 和 1 的数量相等”的那些子串吗？不对，题目描述只是说“0 和 1 数量相等”，没有要求必须交替。但示例中给出的子串都是交替的。让我们检查上面多出来的子串：

  • s[0..7]="00110011"：0:4,1:4，满足，但为什么示例没算？因为题目要求是“连续子串”，但可能示例只列出了“最长的满足条件的子串”吗？不，题目要求统计所有。但示例输出是 6，而我们找到了 9 个。所以我们必须重新理解题目。

再读示例：示例 1 中列出了 6 个子串，它们分别是：

  • "0011"（索引0-3）
  • "01"（索引1-2）
  • "1100"（索引2-5）
  • "10"（索引3-4）
  • "0011"（索引4-7）
  • "01"（索引5-6）

注意，这些子串有一个共同特点：它们都是“由连续的一段 0 和紧接着连续的一段 1 组成（或连续的一段 1 和紧接着连续的一段 0 组成），且这两段的长度相等”。换句话说，这些子串是“成对出现的连续相同字符组”。

比如 "0011" 是 2 个 0 后接 2 个 1；"01" 是 1 个 0 后接 1 个 1；"1100" 是 2 个 1 后接 2 个 0。

所以题目真正的意思是：统计那些“可以分成连续的两段，前一段全为 0，后一段全为 1，或者前一段全为 1，后一段全为 0，并且两段长度相等”的子串个数。
这实际上是一个更特殊的问题，而不是简单的 0 和 1 数量相等。

修正问题理解

题目实际上是 Count Binary Substrings（LeetCode 696）。
它要求统计满足以下条件的连续子串个数：

  • 子串中所有 0 和所有 1 都是连续分组出现的（即要么是 0...01...1，要么是 1...10...0）。
  • 且 0 的数量等于 1 的数量。

也就是说，子串必须是“连续的相同字符块”的对，且两个块的长度相等。

示例 1 详细解释：
s = "00110011"

  • 从左到右，连续字符块长度：["00", "11", "00", "11"]，对应长度 [2,2,2,2]。
  • 对于相邻两块，比如前两块 "00" 和 "11"，可以形成的有效子串有：从第一块末尾和第二块开头各取相同长度。长度为 2 时，取 "0011"；长度为 1 时，取 "01"（从第一块最后一个 0 和第二块第一个 1）。
  • 更一般地，对于相邻两块，假设长度分别为 a 和 b，那么它们能贡献的有效子串个数为 min(a, b)。

所以算法修正为：

  1. 将字符串按连续相同字符分组，记录每组的长度。
  2. 遍历相邻的组，将 min(prev_len, curr_len) 累加到答案中。

以 s = "00110011" 为例：
分组长度：[2,2,2,2]
相邻对：

  • 第1组和第2组：min(2,2)=2 → 子串 "0011" 和 "01"
  • 第2组和第3组：min(2,2)=2 → 子串 "1100" 和 "10"
  • 第3组和第4组：min(2,2)=2 → 子串 "0011" 和 "01"
    总计数 = 2+2+2 = 6，符合示例。

动态规划解法

我们可以用动态规划的思想来实现上述分组过程，而不必显式存储所有组长度。

定义：

  • 用 prev 表示上一组连续相同字符的长度。
  • 用 curr 表示当前组连续相同字符的长度。
  • 遍历字符串，当字符变化时，更新 prev = curr, curr = 1；当字符相同时，curr++。
  • 每次字符变化时，就可以累加 min(prev, curr) 到答案中。

注意：累加操作发生在检测到字符变化时，但此时 prev 是上一组的长度，curr 是当前组已累积的长度（即新组的当前长度）。实际上，我们是在遇到新组开始时，累加上一组和当前组能形成的子串数。

算法步骤：

  1. 初始化 prev = 0, curr = 1, result = 0。
  2. 从索引 1 开始遍历字符串 s：
    • 如果 s[i] == s[i-1]，说明当前字符与前一字符相同，当前组长度增加：curr++。
    • 如果 s[i] != s[i-1]，说明字符变化，开始新的一组：
      • 此时，上一组长度为 prev，当前组（新组）已有长度为 curr（但注意，新组才刚开始，为什么 curr 不为 1？这里需要调整逻辑）。
        实际上，我们需要在字符变化时，将 curr 赋值给 prev，然后重置 curr = 1，并累加 min(prev, curr)？不对，因为此时新组才刚开始，curr 是 1，而 prev 是旧组的长度，累加 min(prev, curr) 得到的是 1，但实际应累加的是 min(prev, curr) 其中 curr 是新组的完整长度，但现在还不知道。所以需要在下一轮变化时累加。

正确做法：
记录两个变量：currentRunLength 和 previousRunLength。
遍历字符串，统计当前连续相同字符的长度。当字符变化时，用前一段长度和当前段长度的最小值来累加答案，然后更新前一段长度为当前段长度，重置当前段长度为 1。

具体：

  1. 初始化 ans = 0, prev = 0, curr = 1。
  2. 从 i=1 到 n-1：
    • 如果 s[i] == s[i-1]，则 curr++。
    • 否则（s[i] != s[i-1]）：
      • ans += min(prev, curr) // 用上一段和当前段的最小值累加
      • prev = curr
      • curr = 1
  3. 循环结束后，还需要再加一次：ans += min(prev, curr)。
  4. 返回 ans。

示例推导（s="00110011"）：
i=0: curr=1
i=1: s[1]==s[0] -> curr=2
i=2: s[2]!=s[1] -> ans+=min(prev=0,curr=2)=0, prev=2, curr=1
i=3: s[3]==s[2] -> curr=2
i=4: s[4]!=s[3] -> ans+=min(2,2)=2, prev=2, curr=1
i=5: s[5]==s[4] -> curr=2
i=6: s[6]!=s[5] -> ans+=min(2,2)=4, prev=2, curr=1
i=7: s[7]==s[6] -> curr=2
结束：ans+=min(2,2)=6

结果正确。

复杂度分析

  • 时间复杂度：O(n)，只需一次遍历字符串。
  • 空间复杂度：O(1)，只用了常数个额外变量。

总结

本题的关键在于理解题目要求的“0 和 1 数量相等的子串”实际上是指“由连续的一段 0 和连续的一段 1 组成（或反之），且两段长度相等”的子串。
通过分组计数，并累加相邻两组长度的最小值，即可得到答案。这种方法简洁高效，是典型的线性动态规划思想（状态由当前组长度和上一组长度决定）。

线性动态规划：统计二进制子串中0和1数量相等的子串个数 问题描述 给定一个二进制字符串 s ，它仅由字符 '0' 和 '1' 组成。要求统计并返回其中“0 和 1 数量相等”的非空连续子串的个数。 示例 1： 输入：s = "00110011" 输出：6 解释：满足条件的子串有： "0011" (子串 [ 0,3 ]) "01" (子串 [ 1,2 ]) "1100" (子串 [ 2,5 ]) "10" (子串 [ 3,4 ]) "0011" (子串 [ 4,7 ]) "01" (子串 [ 5,6 ]) 示例 2： 输入：s = "10101" 输出：4 解释：满足条件的子串有： "10" (子串 [ 0,1 ]) "01" (子串 [ 1,2 ]) "10" (子串 [ 2,3 ]) "01" (子串 [ 3,4 ]) 注意：子串必须是连续的一段字符。 解题思路 这是一个计数问题，要求找出所有满足“0 和 1 数量相等”的连续子串。 我们可以将其转化为“前缀和”的思想，但这里 0 和 1 的数量要相等，而不是和为零。 一个巧妙的转换是：将字符 '0' 视为 -1，将 '1' 视为 1。这样，一个子串中 0 和 1 数量相等，就等价于这个子串的“和”为 0。 于是，问题变成了：在转换后的数组中，找出所有和为 0 的连续子数组的个数。 这可以通过动态规划配合哈希表来高效求解，其核心是“前缀和 + 哈希计数”。 详细步骤 步骤 1：问题转换 定义一个整数数组 arr ，长度与字符串 s 相同。 遍历字符串 s ，如果 s[i] == '0' ，则 arr[i] = -1 ；如果 s[i] == '1' ，则 arr[i] = 1 。 转换后的问题 ：在数组 arr 中，统计和为 0 的连续子数组的个数。 步骤 2：前缀和的定义 定义前缀和 prefixSum[i] 表示从 arr[0] 到 arr[i] 的元素之和（包括两端）。 即 prefixSum[i] = arr[0] + arr[1] + ... + arr[i] 。 特别地，定义 prefixSum[-1] = 0 ，表示在开始之前的前缀和为 0。 关键观察 ： 对于任意子数组 arr[j...i] （从索引 j 到 i，包含两端），其和为： 当这个和为 0 时，有 prefixSum[i] = prefixSum[j-1] 。 结论 ： 满足条件的子数组，其结束位置 i 对应的前缀和，等于某个更早位置（j-1）的前缀和。 所以，我们需要统计，对于每个结束位置 i，有多少个开始位置 j（j ≤ i），使得 prefixSum[j-1] 等于 prefixSum[i] 。 步骤 3：动态规划（哈希表计数） 我们可以一边计算前缀和，一边用哈希表记录之前出现过的各个前缀和值的次数。 算法流程 ： 初始化哈希表 countMap ，键为前缀和的值，值为该前缀和出现的次数。初始时， countMap[0] = 1 ，表示前缀和为 0 在索引 -1 时出现了一次。 初始化 currentSum = 0 ，表示当前的前缀和。 初始化 result = 0 ，用于累计满足条件的子串个数。 遍历字符串 s 的每个字符： 如果当前字符是 '0' ，则 currentSum -= 1 。 如果当前字符是 '1' ，则 currentSum += 1 。 检查 currentSum 是否已经在 countMap 中出现过： 如果出现过，说明存在若干个开始位置，使得从那个位置到当前位置的子串和为 0。这些开始位置的个数，就是 countMap[currentSum] 的值。将它们加到 result 中。 将当前 currentSum 的出现次数加 1，更新 countMap 。 遍历结束后， result 即为所求。 原理 ： 哈希表 countMap 记录了在遍历过程中，每个前缀和值出现了多少次。当我们计算到位置 i 时， currentSum 是 prefixSum[i] 。如果之前某个位置 j-1 也有相同的前缀和，那么子串 arr[j...i] 的和就是 0。而 countMap[currentSum] 就记录了这样的 j-1 的个数（即开始位置的选择数）。 步骤 4：示例推导 以 s = "00110011" 为例： | 索引 i | 字符 | currentSum 变化 | currentSum 值 | countMap 当前状态（前缀和 -> 出现次数） | 新增满足条件的子串个数 | |--------|------|-----------------|---------------|-----------------------------------------|------------------------| | 初始化 | | | 0 | {0:1} | 0 | | 0 | '0' | -1 | -1 | {0:1, -1:1} | 0 | | 1 | '0' | -1 | -2 | {0:1, -1:1, -2:1} | 0 | | 2 | '1' | +1 | -1 | {0:1, -1:2, -2:1} | 1 (因为 -1 出现过 1 次，对应子串 s[ 1..2 ]="01") | | 3 | '1' | +1 | 0 | {0:2, -1:2, -2:1} | 2 (因为 0 出现过 1 次，对应子串 s[ 0..3 ]="0011") | | 4 | '0' | -1 | -1 | {0:2, -1:3, -2:1} | 3 (因为 -1 出现过 2 次，对应子串 s[ 2..4]="110" 和 s[ 1..4 ]="0110"，但注意："110" 中 0 和 1 数量不等？这里需要验证) | 等一下，这里出现了问题！让我们仔细分析。 验证 ： 当 i=4 时， currentSum = -1 ，之前出现过 2 次（在 i=0 和 i=2）。 从 j-1 = 0 到 i=4，对应子串 s[ 1..4 ] = "0110"（0:2个, 1:2个），确实满足条件。 从 j-1 = 2 到 i=4，对应子串 s[ 3..4 ] = "10"（0:1个, 1:1个），也满足条件。 所以 i=4 时新增 2 个，总共 1+2+2=5 个？但示例答案是 6。继续推导： | 索引 i | 字符 | currentSum 值 | countMap 更新前 | 新增个数 | 累计 result | 具体新增的子串（结束于 i） | |--------|------|---------------|-----------------|----------|-------------|---------------------------| | 5 | '0' | -2 | {0:2, -1:3, -2:1} | 1 (因为 -2 出现过 1 次) | 6 | s[ 2..5 ]="1100" (0:2,1:2) | | 6 | '1' | -1 | {0:2, -1:3, -2:2} | 3 (因为 -1 出现过 3 次) | 9 | s[ 3..6]="1001"? 不，应该检查：j-1 对应前缀和为 -1 的位置有 i=0,2,4。子串分别为 s[ 1..6]="011001"（不等）, s[ 3..6]="1001"（不等）, s[ 5..6 ]="01"（等）。所以只有最后一个满足。所以这里计算有误。 | 发现我们多算了！因为我们需要子串中 0 和 1 的数量相等，对应转换后数组的和为 0。但我们的方法统计的是“前缀和相等”的情况，这确实对应和为 0 的子串，但必须确保子串长度至少为 2（因为单个字符不可能相等）。上面的推导中，有一些子串其实不满足数量相等，比如 "110"（0:1,1:2）并不相等，为什么会被计入？ 仔细检查 ： 转换数组：s="00110011" -> arr = [ -1, -1, 1, 1, -1, -1, 1, 1 ] 前缀和： i=-1: 0 i=0: -1 i=1: -2 i=2: -1 i=3: 0 i=4: -1 i=5: -2 i=6: -1 i=7: 0 查找和为 0 的子串： prefixSum[ 3] = 0，与 prefixSum[ -1]=0 相等 → 子串 s[ 0..3 ]="0011"（长度4，0:2,1:2）✔ prefixSum[ 7] = 0，与 prefixSum[ -1]=0 相等 → 子串 s[ 0..7 ]="00110011"（长度8，0:4,1:4）✔ prefixSum[ 7] = 0，与 prefixSum[ 3]=0 相等 → 子串 s[ 4..7 ]="0011"（长度4，0:2,1:2）✔ prefixSum[ 2] = -1，与 prefixSum[ 0]=-1 相等 → 子串 s[ 1..2 ]="01"（长度2，0:1,1:1）✔ prefixSum[ 4] = -1，与 prefixSum[ 0]=-1 相等 → 子串 s[ 1..4 ]="0110"（长度4，0:2,1:2）✔ prefixSum[ 4] = -1，与 prefixSum[ 2]=-1 相等 → 子串 s[ 3..4 ]="10"（长度2，0:1,1:1）✔ prefixSum[ 6] = -1，与 prefixSum[ 0]=-1 相等 → 子串 s[ 1..6 ]="011001"（长度6，0:3,1:3）✔ prefixSum[ 6] = -1，与 prefixSum[ 2]=-1 相等 → 子串 s[ 3..6 ]="1001"（长度4，0:2,1:2）✔ prefixSum[ 6] = -1，与 prefixSum[ 4]=-1 相等 → 子串 s[ 5..6 ]="01"（长度2，0:1,1:1）✔ 我们找到了 9 个子串，但示例说只有 6 个。为什么？ 问题在于 ：示例中只统计“连续的 0 和连续的 1 的组交替出现，且相邻两组 0 和 1 的数量相等”的那些子串吗？不对，题目描述只是说“0 和 1 数量相等”，没有要求必须交替。但示例中给出的子串都是交替的。让我们检查上面多出来的子串： s[ 0..7 ]="00110011"：0:4,1:4，满足，但为什么示例没算？因为题目要求是“连续子串”，但可能示例只列出了“最长的满足条件的子串”吗？不，题目要求统计所有。但示例输出是 6，而我们找到了 9 个。所以我们必须重新理解题目。 再读示例 ：示例 1 中列出了 6 个子串，它们分别是： "0011"（索引0-3） "01"（索引1-2） "1100"（索引2-5） "10"（索引3-4） "0011"（索引4-7） "01"（索引5-6） 注意，这些子串有一个共同特点：它们都是“由连续的一段 0 和紧接着连续的一段 1 组成（或连续的一段 1 和紧接着连续的一段 0 组成），且这两段的长度相等”。换句话说，这些子串是“成对出现的连续相同字符组”。 比如 "0011" 是 2 个 0 后接 2 个 1；"01" 是 1 个 0 后接 1 个 1；"1100" 是 2 个 1 后接 2 个 0。 所以题目真正的意思是 ：统计那些“可以分成连续的两段，前一段全为 0，后一段全为 1，或者前一段全为 1，后一段全为 0，并且两段长度相等”的子串个数。 这实际上是一个更特殊的问题，而不是简单的 0 和 1 数量相等。 修正问题理解 题目实际上是 Count Binary Substrings （LeetCode 696）。 它要求统计满足以下条件的连续子串个数： 子串中所有 0 和所有 1 都是连续分组出现的（即要么是 0...01...1，要么是 1...10...0）。 且 0 的数量等于 1 的数量。 也就是说，子串必须是“连续的相同字符块”的对，且两个块的长度相等。 示例 1 详细解释 ： s = "00110011" 从左到右，连续字符块长度：[ "00", "11", "00", "11"]，对应长度 [ 2,2,2,2 ]。 对于相邻两块，比如前两块 "00" 和 "11"，可以形成的有效子串有：从第一块末尾和第二块开头各取相同长度。长度为 2 时，取 "0011"；长度为 1 时，取 "01"（从第一块最后一个 0 和第二块第一个 1）。 更一般地，对于相邻两块，假设长度分别为 a 和 b，那么它们能贡献的有效子串个数为 min(a, b)。 所以算法修正为 ： 将字符串按连续相同字符分组，记录每组的长度。 遍历相邻的组，将 min(prev_ len, curr_ len) 累加到答案中。 以 s = "00110011" 为例 ： 分组长度：[ 2,2,2,2 ] 相邻对： 第1组和第2组：min(2,2)=2 → 子串 "0011" 和 "01" 第2组和第3组：min(2,2)=2 → 子串 "1100" 和 "10" 第3组和第4组：min(2,2)=2 → 子串 "0011" 和 "01" 总计数 = 2+2+2 = 6，符合示例。 动态规划解法 我们可以用动态规划的思想来实现上述分组过程，而不必显式存储所有组长度。 定义 ： 用 prev 表示上一组连续相同字符的长度。 用 curr 表示当前组连续相同字符的长度。 遍历字符串，当字符变化时，更新 prev = curr , curr = 1 ；当字符相同时， curr++ 。 每次字符变化时，就可以累加 min(prev, curr) 到答案中。 注意 ：累加操作发生在检测到字符变化时，但此时 prev 是上一组的长度， curr 是当前组已累积的长度（即新组的当前长度）。实际上，我们是在遇到新组开始时，累加上一组和当前组能形成的子串数。 算法步骤 ： 初始化 prev = 0 , curr = 1 , result = 0 。 从索引 1 开始遍历字符串 s： 如果 s[i] == s[i-1] ，说明当前字符与前一字符相同，当前组长度增加： curr++ 。 如果 s[i] != s[i-1] ，说明字符变化，开始新的一组： 此时，上一组长度为 prev ，当前组（新组）已有长度为 curr （但注意，新组才刚开始，为什么 curr 不为 1？这里需要调整逻辑）。 实际上，我们需要在字符变化时，将 curr 赋值给 prev ，然后重置 curr = 1 ，并累加 min(prev, curr)？不对，因为此时新组才刚开始，curr 是 1，而 prev 是旧组的长度，累加 min(prev, curr) 得到的是 1，但实际应累加的是 min(prev, curr) 其中 curr 是新组的完整长度，但现在还不知道。所以需要在下一轮变化时累加。 正确做法 ： 记录两个变量： currentRunLength 和 previousRunLength 。 遍历字符串，统计当前连续相同字符的长度。当字符变化时，用前一段长度和当前段长度的最小值来累加答案，然后更新前一段长度为当前段长度，重置当前段长度为 1。 具体 ： 初始化 ans = 0 , prev = 0 , curr = 1 。 从 i=1 到 n-1： 如果 s[ i] == s[ i-1]，则 curr++ 。 否则（s[ i] != s[ i-1 ]）： ans += min(prev, curr) // 用上一段和当前段的最小值累加 prev = curr curr = 1 循环结束后，还需要再加一次： ans += min(prev, curr) 。 返回 ans 。 示例推导 （s="00110011"）： i=0: curr=1 i=1: s[ 1]==s[ 0 ] -> curr=2 i=2: s[ 2]!=s[ 1 ] -> ans+=min(prev=0,curr=2)=0, prev=2, curr=1 i=3: s[ 3]==s[ 2 ] -> curr=2 i=4: s[ 4]!=s[ 3 ] -> ans+=min(2,2)=2, prev=2, curr=1 i=5: s[ 5]==s[ 4 ] -> curr=2 i=6: s[ 6]!=s[ 5 ] -> ans+=min(2,2)=4, prev=2, curr=1 i=7: s[ 7]==s[ 6 ] -> curr=2 结束：ans+=min(2,2)=6 结果正确。 复杂度分析 时间复杂度：O(n)，只需一次遍历字符串。 空间复杂度：O(1)，只用了常数个额外变量。 总结 本题的关键在于理解题目要求的“0 和 1 数量相等的子串”实际上是指“由连续的一段 0 和连续的一段 1 组成（或反之），且两段长度相等”的子串。 通过分组计数，并累加相邻两组长度的最小值，即可得到答案。这种方法简洁高效，是典型的线性动态规划思想（状态由当前组长度和上一组长度决定）。