解决K长度二进制码包含问题的方法

本文深入剖析LeetCode 1461题的高效解法，直击暴力枚举生成全部2ᵏ个二进制码所导致的指数级时间与空间开销痛点，巧妙融合滑动窗口、整数哈希映射和哈希集合去重，在O(n)线性时间内完成判定——将每个长度为k的二进制子串动态转化为[0, 2ᵏ−1]内的唯一整数，通过位运算实时更新窗口值，彻底规避字符串切片、列表查找与重复构造，让算法在k=20甚至更大规模下依然稳定高效，是理解哈希优化与滑动窗口进阶应用的绝佳范例。

本文详解 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) 插入与去重：

1. 数学映射：每个长度为 k 的二进制子串可唯一对应一个 [0, 2ᵏ−1] 范围内的整数（如 "101" → 5）；
2. 滑动窗口整数更新：不重建子串，而是动态维护当前窗口对应的整数值：
   • 设当前值为 value，新加入位为 digit（0 或 1），则新值 = (value << 1 | digit) & ((1 << k) - 1)；
   • 等价于 (value * 2 + digit) % (1 << k)，利用位运算高效截断高位；
3. 哈希集合计数：用 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 << k) - 1) 是位掩码操作，等价于 % (1 << k)，但位运算更快且无负数风险；
• 使用 | 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ᵏ 可能达百万级，此时内存虽可接受，但暴力枚举绝对不可行——本解法正是为此场景而生。

总结：本题本质是「滑动窗口 + 哈希去重」的经典应用。抓住“二进制子串 ↔ 整数映射”这一抽象，摒弃字符串操作，用位运算维持状态，辅以集合与早停策略，即可优雅通过所有测试用例，包括最大规模输入。

好了，本文到此结束，带大家了解了《解决K长度二进制码包含问题的方法》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！