本文详解 leetcode 1461 题的优化思路：避免暴力枚举与列表操作，改用滑动窗口 + 整数哈希 + 集合去重，在 o(n) 时间内完成判断。
本文详解 leetcode 1461 题的优化思路：避免暴力枚举与列表操作，改用滑动窗口 + 整数哈希 + 集合去重，在 o(n) 时间内完成判断。
原解法虽逻辑正确，但存在严重性能瓶颈：它预先生成全部 $2^k$ 个长度为 $k$ 的二进制字符串（如 k=20 时达 1048576 个），并用 Python 列表存储；随后在滑动窗口中对每个子串执行 binary.remove(sSoFar) —— 该操作平均时间复杂度为 $O(2^k)$，导致整体复杂度飙升至 $O(n \cdot 2^k)$，面对长字符串（如 k=20, len(s)≈200）必然超时。
核心优化方向有三：
- 空间与查找效率升级： 放弃字符串列表，改用 set() 存储已见的二进制码对应的整数值（如 "101" → 5），使插入与查重均为 $O(1)$ 平均时间；
- 动态窗口值计算： 不重复切片和转换子串（如 s[i:i+k] → int(..., 2)），而是维护一个整型变量 value，通过位运算实时更新当前窗口代表的数值；
- 提前终止机制： 一旦集合大小达到 $2^k$，立即返回 True，无需遍历完整个字符串。
✅ 优化后的滑动窗口实现
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if k > len(s):
return False
# 目标总数：2^k
total = 1 << k # 等价于 2 ** k，位运算更高效
seen = set() # 存储已出现的 k 位二进制数对应整数值
value = 0 # 当前窗口对应的整数值
# 预处理前 k-1 位（用于初始化）
for i in range(k - 1):
value = (value << 1) | int(s[i])
# 滑动窗口：从第 k-1 位开始（索引 0 起）
mod = total # 用于截断高位，等价于 mask = (1 << k) - 1，但此处用模更直观
for i in range(k - 1, len(s)):
# 更新窗口值：左移一位，加入新 bit，再取模保留低 k 位
value = ((value << 1) | int(s[i])) & (mod - 1)
seen.add(value)
# 提前终止：已收集全部 2^k 种组合
if len(seen) == total:
return True
return False? 关键技巧说明：
- & (mod - 1) 是位掩码操作（因 mod = 2^k，故 mod - 1 是形如 0b111...1（共 k 个 1）的掩码），比 % mod 更快且语义更清晰；
- 初始化 value 时仅处理前 k-1 位，主循环中每次添加第 k 位，自然构成完整窗口；
- 对于 k = 1，循环仍正确：k-1 = 0，跳过预处理，首字符直接参与计算。
⚠️ 注意事项与边界处理
- 输入校验优先： 若 k > len(s)，不可能覆盖所有 $2^k$ 个子串，直接返回 False；
- 整数溢出无忧： Python 整数无位宽限制，但 & (mod - 1) 确保 value 始终在 [0, 2^k - 1] 范围内，语义明确；
- 集合容量即答案： len(seen) == total 是充要条件，无需额外校验缺失项；
- 避免字符串拼接： 原解法中 sSoFar += s[j] 和 sSoFar[1:] 是 $O(k)$ 操作，本解法全程使用整数运算，彻底规避。
✅ 性能对比总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否可通过 k=20 大数据？ |
|---|---|---|---|
| 原始暴力解法 | $O(n \cdot 2^k)$ | $O(2^k)$ | ❌ 超时（n≈200, 2^20≈1e6） |
| 优化滑动窗口 | $O(n)$ | $O(2^k)$ | ✅ 稳定通过（n≈200 → 仅 200 次迭代） |
该方案将问题从指数级降为线性，是典型「用空间换时间 + 数学建模优化」的工程实践范例。掌握此类滑动窗口整数哈希技巧，对解决字符串编码、滚动哈希（如 Rabin-Karp）、位图状态压缩等问题均有重要迁移价值。
