K长度二进制子串问题解法

本文深入剖析LeetCode 1461题的高效解法，直击暴力枚举导致的严重性能陷阱——当k增大时，传统方法因生成全部2^k个二进制串并频繁进行O(2^k)列表删除操作而迅速超时；作者巧妙融合滑动窗口、整数哈希（位运算动态维护窗口值）和集合去重，在O(n)线性时间内完成判定，并加入提前终止机制，让算法既简洁又强悍，是理解时空优化与位运算实战的绝佳范例。

本文详解 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）必然超时。

核心优化方向有三：

1. 空间与查找效率升级： 放弃字符串列表，改用 set() 存储已见的二进制码对应的整数值（如 "101" → 5），使插入与查重均为 $O(1)$ 平均时间；
2. 动态窗口值计算： 不重复切片和转换子串（如 s[i:i+k] → int(..., 2)），而是维护一个整型变量 value，通过位运算实时更新当前窗口代表的数值；
3. 提前终止机制： 一旦集合大小达到 $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)$ 操作，本解法全程使用整数运算，彻底规避。

✅ 性能对比总结

该方案将问题从指数级降为线性，是典型「用空间换时间 + 数学建模优化」的工程实践范例。掌握此类滑动窗口整数哈希技巧，对解决字符串编码、滚动哈希（如 Rabin-Karp）、位图状态压缩等问题均有重要迁移价值。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。