题目描述
思路解析
一句话答案：LeetCode 1016 子串能表示 1 到 N 的二进制串：用子串检查加剪枝，只验后半段 (n/2, n] 的数是不是 s 的子串，前半段是它们的前缀自动满足。O(n·|s|·log n) 时间、O(log n) 空间。
s 里要翻得出 1 到 n 每个数的二进制
题目给一个只含 0 和 1 的字符串 s 和一个正整数 n。要把 1、2 一直到 n 每个数写成二进制，看它们是不是都能在 s 里找到一段连续字符跟它一模一样——子串就是连续的一段、中间不能断。全找得到返回 true，有一个找不到就 false。题面 s=0110、n=3 返回 true（1、10、11 都在），n=4 返回 false（4 的 100 找不到）。
从 1 挨个查到 n，n 一大这法子还扛得住吗
从 1 到 n 一个个查：把数字转成二进制，去 s 里搜有没有这一段。麻烦在 n 可以很大，逐个搜像没尽头。但有个硬上限压着——(n/2, n] 这半段的数都大于 n/2，两串若从 s 同一处起头，短的必是长的前缀；可这里谁翻倍都越过 n、互不为前缀，就只能各占 s 里一个不同起点。s 一共才 |s| 个起点，n 一旦超过 2 倍 |s| 便塞不下、必有一个落空，直接返回 false。真正要查的 n 顶多 2|s|，两千以内。
为什么只查后半段的数，前半段能整段跳过
更省的一刀是：连 1 到 n/2 这下半段都不用查。任取一个 x≤n/2，把它的二进制末尾不断补 0（等于每次翻倍），迟早会落进 (n/2, n] 得到某个 y；而 bin(x) 正好是 bin(y) 砍掉末尾那几个 0 剩下的前缀。只要 y 的二进制是 s 的子串，它开头那一截 bin(x) 自然也在 s 里。所以下半段每个数都被上半段某个数顺带盖住了，只需验 (n/2, n] 上半段就够，检查量砍半。
先短路，再逐个转二进制拿窗口在 s 上滑
合起来的流程很短。先短路：n 大于 2 倍 |s| 直接判 false。否则从 n 往下数到 n/2+1，逐个取它的最短二进制（去掉 0b 前缀、不带前导零），拿这段定宽的模式在 s 上从左往右滑，一格一格比，看有没有哪一段和它完全相同。中途任意一个数在 s 里滑到头都没配上，立刻返回 false；上半段全部配上，才返回 true。
s=0110、n=3，看 1 是怎么被顺带盖掉的
拿题面 s=0110、n=3 走一遍。2 倍 |s| 是 8，n=3 没超，不短路。n/2=1，要查 3 和 2。先看 3，二进制 11，滑宽 2 的窗口：01 不是、11 对上（下标 1 到 2）。再看 2，二进制 10，滑到下标 2 到 3 截出 10，配上。上半段都在，返回 true——1 全程没查，它的二进制 1 是 2 的 10 的前缀，顺带盖掉。若 n 换成 4，多出的 4 是 100，滑宽 3 只截得出 011、110，没有 100，直接返回 false。
二进制取最短那版，带着前导零就和 s 对不上
几处一错就整道判反。二进制一定取最短那版：Python 用 bin(i)[2:] 去掉 0b、C++ 砍掉前导零；留着前导零就和 s 里的子串对不上，本能找到的数会被漏判。也别只顾逐个查而丢了砍半——下半段是上半段前缀，只验 (n/2, n]。还有几个边界：s 只有一个 0、n=1 时里头没有 1，返回 false；s 里有个 1、n=1 就已满足；n 超过 2 倍 |s| 直接出局。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套:逐个数字转二进制，再用一个等长窗口在 s 上滑动找它。一个找不到就出局，全找到才算 true。下面每帧都在套它。
先把 s 等于 100110100 摆好，下标 0 到 8。右边清单列着 1 到 5 各自的二进制，现在全是「待查」。我们一个一个来，把它们的二进制都在 s 里找一遍。
轮到数字 1，它的二进制是 1，一共 1 位。接下来用一个宽 1 的窗口，从 s 最左边开始往右滑，看哪一段正好是 1。
窗口滑到 [0, 0]，框住的是 1，正好等于目标 1，命中！数字 1 在 s 里确实出现，这一段标绿。
数字 1 搞定，它的二进制 1 落在 s 的 [0, 0] 这段。右边清单给 1 打上勾，目前 1 个都找到了，接着查下一个。
轮到数字 2，它的二进制是 10，一共 2 位。接下来用一个宽 2 的窗口，从 s 最左边开始往右滑，看哪一段正好是 10。
窗口滑到 [0, 1]，框住的是 10，正好等于目标 10，命中！数字 2 在 s 里确实出现，这一段标绿。
数字 2 搞定，它的二进制 10 落在 s 的 [0, 1] 这段。右边清单给 2 打上勾，目前 2 个都找到了，接着查下一个。
轮到数字 3，它的二进制是 11，一共 2 位。接下来用一个宽 2 的窗口，从 s 最左边开始往右滑，看哪一段正好是 11。
窗口在 [0, 1]，框住的是 10，和目标 11 不一样，没命中。窗口整体往右挪一格，继续比。
窗口在 [1, 2]，框住的是 00，和目标 11 不一样，没命中。窗口整体往右挪一格，继续比。
窗口在 [2, 3]，框住的是 01，和目标 11 不一样，没命中。窗口整体往右挪一格，继续比。
窗口滑到 [3, 4]，框住的是 11，正好等于目标 11，命中！数字 3 在 s 里确实出现，这一段标绿。
数字 3 搞定，它的二进制 11 落在 s 的 [3, 4] 这段。右边清单给 3 打上勾，目前 3 个都找到了，接着查下一个。
轮到数字 4，它的二进制是 100，一共 3 位。接下来用一个宽 3 的窗口，从 s 最左边开始往右滑，看哪一段正好是 100。
窗口滑到 [0, 2]，框住的是 100，正好等于目标 100，命中！数字 4 在 s 里确实出现，这一段标绿。
数字 4 搞定，它的二进制 100 落在 s 的 [0, 2] 这段。右边清单给 4 打上勾，目前 4 个都找到了，接着查下一个。
轮到数字 5，它的二进制是 101，一共 3 位。接下来用一个宽 3 的窗口，从 s 最左边开始往右滑，看哪一段正好是 101。
窗口在 [0, 2]，框住的是 100，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
窗口在 [1, 3]，框住的是 001，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
窗口在 [2, 4]，框住的是 011，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
窗口在 [3, 5]，框住的是 110，和目标 101 不一样，没命中。窗口整体往右挪一格，继续比。
窗口滑到 [4, 6]，框住的是 101，正好等于目标 101，命中！数字 5 在 s 里确实出现，这一段标绿。
数字 5 搞定，它的二进制 101 落在 s 的 [4, 6] 这段。右边清单给 5 打上勾，目前 5 个全部找到，没有下一个了，进入总判断、准备返回 true。
1 到 5 全都在 s 里找到了二进制对应的子串，清单一个不漏全打了勾。没有任何一个数字落空，所以答案是 true。要是中途有一个找不到，那一刻就该直接返回 false。
边界先想清:只有 0 找不到 1、单个 1 能满足、n 超过 2 倍 s 长度直接出局。
面试重点:说清约束如何把规模锁死，以及正反两种枚举方向。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def queryString(self, s: str, n: int) -> bool: if n > 2 * len(s): return False return all(bin(i)[2:] in s for i in range(n, n // 2, -1))复杂度
- 时间：O(n · |s| · log n)，上半段约 n/2 个数(O(n)),每个二进制长 O(log n)，在长度 |s| 的串里滑窗逐位比较 O(|s|·log n);|s|≤1000 时可视作常数,实践界约 O(n log n)
- 空间：O(log n)，只存当前数字的二进制串，长度 O(log n)
易错点
面试追问把动画讲成自己的话
追问直接逐个数字 indexOf 查子串，复杂度会不会爆？
追问还有没有不靠子串匹配的思路？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
移动石子直到连续 II
LeetCode 1040 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题