本文详解 leetcode 1461 题的优化思路：避免暴力枚举与列表操作，改用滑动窗口 + 整数哈希 + 集合去重，在 o(n) 时间内判定二进制字符串是否包含全部长度为 k 的子码。
本文详解 leetcode 1461 题的优化思路：避免暴力枚举与列表操作，改用滑动窗口 + 整数哈希 + 集合去重，在 o(n) 时间内判定二进制字符串是否包含全部长度为 k 的子码。
在解决 LeetCode 第 1461 题「Check If a String Contains All Binary Codes of Size K」时，初学者常采用“生成全部 2ᵏ 个二进制字符串 → 逐个检查是否为子串”的暴力策略。该方法逻辑直观，但存在严重性能瓶颈：
- 生成所有长度为 k 的二进制字符串需 O(2ᵏ) 时间与空间；
- 每次 binary.remove(sSoFar) 或 sSoFar in binary 在列表中查找/删除均为 O(2ᵏ) 平均时间复杂度；
- 滑动窗口中还使用了 sSoFar = sSoFar[1:] 字符串切片，每次 O(k)，整体退化为 O(n·k·2ᵏ)，面对 k=20（即 2²⁰ ≈ 100 万）的测试用例必然超时。
✅ 正确解法的核心优化在于 避免显式构造字符串集合，转而用整数表示二进制码，并借助哈希集合实现 O(1) 插入与去重：
- 数学映射：每个长度为 k 的二进制子串可唯一对应一个 [0, 2ᵏ−1] 范围内的整数（如 "101" → 5）；
-
滑动窗口整数更新：不重建子串，而是动态维护当前窗口对应的整数值：
- 设当前值为 value，新加入位为 digit（0 或 1），则新值 = (value
- 等价于 (value * 2 + digit) % (1
- 哈希集合计数：用 set() 存储已出现的整数值，一旦集合大小达到 2ᵏ，立即返回 True。
以下是优化后的 Python 实现（含关键注释）：
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
# 边界判断：若字符串长度不足 k，不可能覆盖所有 k 位码
if len(s) < k:
return False
total = 1 << k # 即 2^k，共需收集的唯一二进制码数量
seen = set() # 存储已出现的整数型二进制码
# 初始化：取前 k-1 位构成初始 value（补前导 0 避免 k==1 时索引错误）
# 更简洁做法：直接从索引 0 开始，用前 k 位初始化 value
value = 0
# 构造初始窗口 [0, k-1] 对应的整数值
for i in range(k):
value = (value << 1) | int(s[i])
seen.add(value)
# 滑动窗口：从第 k 位开始，逐个推进
for i in range(k, len(s)):
# 移除最高位（第 i-k 位），加入新位 s[i]
# 等价于：value = ((value << 1) | int(s[i])) & ((1 << k) - 1)
value = ((value << 1) | int(s[i])) & ((1 << k) - 1)
seen.add(value)
# 提前终止：一旦收集满 2^k 个不同值，立刻返回
if len(seen) == total:
return True
return len(seen) == total? 关键细节说明：
- & ((1
- 使用 | int(s[i]) 替代 + int(s[i]) 更符合位运算语义，语义清晰；
- 提前返回机制（if len(seen) == total: return True）显著提升平均性能，尤其在答案为 True 时无需遍历完整字符串；
- 空间复杂度降至 O(2ᵏ)，时间复杂度严格为 O(n)，与 k 无关（仅哈希表扩容有常数影响）。
⚠️ 注意事项：
- 切勿在循环中使用 list.remove() 或 list.pop(0) —— 它们是 O(n) 操作，会将算法拖入 O(n·2ᵏ) 泥潭；
- 避免字符串拼接（如 sSoFar += s[j]）和切片（如 sSoFar[1:]），它们在 Python 中产生新对象，开销大；
- 当 k 较大（如 ≥ 20）时，2ᵏ 可能达百万级，此时内存虽可接受，但暴力枚举绝对不可行——本解法正是为此场景而生。
总结：本题本质是「滑动窗口 + 哈希去重」的经典应用。抓住“二进制子串 ↔ 整数映射”这一抽象，摒弃字符串操作，用位运算维持状态，辅以集合与早停策略，即可优雅通过所有测试用例，包括最大规模输入。
