LeetCode 696简单双指针 · 滑窗
计数二进制子串 图解题解
这道题到底在问什么
统计 s 中「0 与 1 数量相等、且 0 全连续、1 全连续」的非空子串个数。不同位置的相同子串分别计数。
- 输入
- s = "00110011"
- 输出
- 6
最优解：一步一步想明白
- 3记牢一句话：相邻两段贡献 min(前段长, 本段长)，全部加起来。下面每一帧都在套它。
- 4先看整串八个字符。接下来从左往右扫，把挨在一起、字符相同的归成同一段。
- 5第 1 段开始：下标 0 是字符 "0"，本段长度先记成 1，把它涂绿。
- 6下标 1 还是 "0"，和前一个相同，归进这一段，本段长度变成 2。
- 7下一个字符变了，第 1 段到此封口，"0" 一共连续 2 个。现在该和前一段配对了。
- 8它前面还没有任何段，pre = 0，配不出子串，本段贡献 0，ans 仍是 0。接着把本段长度 2 存进 pre，留给下一段配对。
- 9第 2 段开始：下标 2 是字符 "1"，本段长度先记成 1，把它涂绿。
- 10下标 3 还是 "1"，和前一个相同，归进这一段，本段长度变成 2。
- 11下一个字符变了，第 2 段到此封口，"1" 一共连续 2 个。现在该和前一段配对了。
- 12前一段长 pre = 2，本段长 run = 2，两段能拼出 min(2, 2) = 2 个合法子串。ans 从 0 累加到 2，再把 pre 更新成 2。
- 13第 3 段开始：下标 4 是字符 "0"，本段长度先记成 1，把它涂绿。
- 14下标 5 还是 "0"，和前一个相同，归进这一段，本段长度变成 2。
- 15下一个字符变了，第 3 段到此封口，"0" 一共连续 2 个。现在该和前一段配对了。
- 16前一段长 pre = 2，本段长 run = 2，两段能拼出 min(2, 2) = 2 个合法子串。ans 从 2 累加到 4，再把 pre 更新成 2。
- 17第 4 段开始：下标 6 是字符 "1"，本段长度先记成 1，把它涂绿。
- 18下标 7 还是 "1"，和前一个相同，归进这一段，本段长度变成 2。
- 19已经扫到末尾，第 4 段到此封口，"1" 一共连续 2 个。现在该和前一段配对了。
- 20前一段长 pre = 2，本段长 run = 2，两段能拼出 min(2, 2) = 2 个合法子串。ans 从 4 累加到 6，再把 pre 更新成 2。
- 21整串扫完，分成了四段，长度依次是 2、2、2、2。蓝色就是已经数过的段。
- 22四段产生三对相邻段，每对取较短段：min(2,2) 三次，每次给 2 个，加起来 6 个。
- 23把所有相邻段的 min 累加，得到答案 6，和题目给的输出对上了。
⚠️ 容易写错的地方
✗ 错：把两段长度相加当贡献
✓ 对：取 min(pre, cur)
合法子串两侧必须等长，受较短那段限制
✗ 错：结算后忘了把 pre 换成 cur
✓ 对：每段算完 pre = cur
不更新会拿错的前段长度去配下一段
✗ 错：内层 j 没吃完相同字符就结算
✓ 对：while 把同字符走到底再算 cur
段没封口，长度就是错的
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def countBinarySubstrings(self, s: str) -> int:
n = len(s)
ans = i = 0
pre = 0
while i < n:
j = i + 1
while j < n and s[j] == s[i]:
j += 1
cur = j - i
ans += min(pre, cur)
pre = cur
i = j
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int countBinarySubstrings(string s) {
int n = s.size();
int ans = 0;
int i = 0;
int pre = 0;
while (i < n) {
int j = i + 1;
while (j < n && s[j] == s[i]) {
++j;
}
int cur = j - i;
ans += min(pre, cur);
pre = cur;
i = j;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countBinarySubstrings(String s) {
int n = s.length();
int ans = 0;
int i = 0;
int pre = 0;
while (i < n) {
int j = i + 1;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int cur = j - i;
ans += Math.min(pre, cur);
pre = cur;
i = j;
}
return ans;
}
}复杂度
时间
O(n)
i 与 j 都只单向走一遍，每个字符看一次
空间
O(1)
只用 pre、cur、ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 计数二进制子串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不存所有段长，只用两个变量？+
可以，而且这正是最优写法。扫描时只维护 pre（前一段长）和 cur（当前段长）：遇到字符变化就结算 ans 加 min(pre, cur)，再把 pre 换成 cur、cur 归一。全程 O(1) 空间，不必把 [2,2,2,2] 整个数组存下来。
这题和「最长连续段」类题是一个套路吗？+
都属于「按连续相同元素分组」这一类。先把序列切成若干等值段，再在段长上做文章：这题是相邻段取 min 累加，最长连续段类是取段长最大值。识别出「分组 + 在段长上运算」这个母题，一类题都能套。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 计数二进制子串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。