1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

🕗 发布于 2025-01-23 15:12 算法滑动窗口

在这里插入图片描述

直接存储滑动窗口内的字符串，这样虽然方便，但是时间复杂度和k相关，如果k = n，此时会达到O(n^2)的复杂度。

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> ss;
        for(int l = 0, r = 0; r < s.size(); ++r) {
            if(r - l + 1 == k) {
                ss.insert(s.substr(l, k));
                l++;
            }
        }
        return ss.size() == 1<<k;
    }
};

时间复杂度: O(n*k)
空间复杂度: O(1<<k)

1<<k：相当于pow(2, k)
substr(截取的字符串起始位置, 截取字符串的长度)

原文地址：https://blog.csdn.net/qq_57882997/article/details/145305128

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：老游戏拆解：生化3RE第一章
下一篇：Java 面向对象基础全面解析

[java] java基础-字符串篇
public StringJoiner(间隔符号,开始符号,结束符号)：创建一个StringJoiner对象，指定拼接时的间隔符号，开始符号，结束符号。指JDK中提供的各种功能的Java类，这些类将底
阅读更多2025-01-24
【C++笔记】哈希表底层实现的深度剖析
哈喽，各位小伙伴大家好!上期我们讲了使用红黑树封装map和set。今天我们来讲一下哈希表底层实现的深度剖析。话不多说，我们进入正题！向大厂冲锋unordered_set的声明如下，Key就是unord
阅读更多2025-01-24
板球背后的数据魔法：如何用数据分析提升印度板球比赛策略
随着板球赛事的数据日益增多，分析技术和方法不断进步，数据已经成为理解和预测比赛结果的核心工具。无论是通过分析球员的个人表现、球队的整体策略，还是通过实时的比赛数据预测，板球比赛的未来将更加依赖数据驱动
阅读更多2025-01-24
数据分析 six库
six库是Python的一个兼容性库，旨在帮助开发者更轻松地编写同时兼容Python 2和Python 3的代码。它是由Ben Hoyt开发的，最初发布于2010年，并在Python社区中被广泛使用。
阅读更多2025-01-24
系统相关类——java.lang.Runtime 类（二）
小编打算近期更俩三期类的专栏，一些常用的专集类，给大家分好类别总结和详细的代码举例解释。今天是第二个java.lang.Runtime 类我们一直都是以这样的形式，让新手小白轻松理解复杂晦涩的概念，把
阅读更多2025-01-24
pandas基础：基本数据结构
类型，而选择多列时返回的是 DataFrame 类型。这种行为是设计上的选择，目的是为了提供更灵活的数据操作方式。中，当你从DataFrame中选择列时，选择的方式会影响返回的数据类型。具体来说，选择
阅读更多2025-01-24
快慢指针及原理证明(swift实现)
快慢指针是一种双指针技巧，常用于遍历链表或是数组。优势如下：1.线性时间复杂度：快慢指针能够在O(n)时间内完成遍历，比暴力方法更高效。2.实时处理：无需额外存储大规模数据，可以在流式日志处理中使
阅读更多2025-01-24
【数据库】详解MySQL数据库中索引的本质与底层原理
这个过程叫寻道，所消耗的时间叫做寻道时间。答：局部性原理：当一个数据被用到时，其附近的数据被用到的概率会增大，所以操作系统为了提高效率，读取数据时往往不是按需读取，而是每次都会预读，即使只需要一个字节
阅读更多2025-01-24
如何处理langcleanupsysprepaction.dll文件的丢失与损坏问题
在使用Windows操作系统时，有时可能会遇到一些DLL文件（动态链接库）丢失或损坏的问题，文件也不例外。这个文件虽然不像一些常见的系统DLL文件那样广为人知，但它对于某些特定的系统操作或应用程序来说
阅读更多2025-01-24
Couchbase UI: Indexes
在Couchbase中，索引的这些指标可以帮助你评估索引的性能和状态。
阅读更多2025-01-24

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

相关文章