给定m个不重复的字符 [a,b,c,d],以及一个长度为n的字符串tbcacbdata滑动窗口

简介: 给定m个不重复的字符 [a,b,c,d],以及一个长度为n的字符串tbcacbdata滑动窗口

题目

给定m个不重复的字符 [a, b, c, d],以及一个长度为n的字符串tbcacbdata, 问能否在这个字符串中找到一个长度为m的连续子串,使得这个子串刚好由上面m个字符组成,顺序无所谓,返回任意满足条件的一个子串的起始位置,未找到返回-1。比如上面这个例子,返回3。

本题的子串需要满足长度为m,字符不重复,可以使用长为m的滑动窗口遍历字符串,窗口内每个字符都要出现一次,如果符合条件,就返回窗口起始位置。

滑动窗口算法

滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。

假设有数组 [a b c d e f g h ],一个大小为 3 的滑动窗口在其上滑动,则有:

[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]

一般情况下就是使用这个窗口在数组的合法区间内进行滑动,同时动态地记录一些有用的数据,很多情况下,能够极大地提高算法地效率。

代码

/**
     * 给定m个不重复的字符 [a, b, c, d],以及一个长度为n的字符串tbcacbdata,
     * 能否在这个字符串中找到一个长度为m的连续子串,使得这个子串刚好由上面m个字符组成.
     * 顺序无所谓,返回任意满足条件的一个子串的起始位置,未找到返回-1。比如上面这个例子,acbd,3.
     *
     * @param ch
     * @param s
     * @return
     */
    private int findIndex(char[] ch, String s) {
        int targetCharSize = ch.length;
        int totalCharSize = s.length();
        if (targetCharSize > totalCharSize) {
            return -1;
        }
        for (int i = 0; i < totalCharSize - targetCharSize; i++) {
            // 滑动窗口的思想,每次取目标数组大小进行比较,不符后再向后移动
            if (checkSubStr(ch, s.substring(i, i + targetCharSize))) {
                return i;
            }
        }
        return -1;
    }
    private boolean checkSubStr(char[] ch, String s) {
        for (int i = 0; i < ch.length; i++) {
            if (s.indexOf(ch[i]) == -1) {
                return false;
            }
        }
        return true;
    }


本篇文章如有帮助到您,请给「翎野君」点个赞,感谢您的支持。


目录
相关文章
|
6月前
|
人工智能 自然语言处理 机器人
大厂RAG面试题:24个RAG八股文。偷偷背下来,毒打面试官 !
大厂RAG面试题:24个RAG八股文。偷偷背下来,毒打面试官 !
大厂RAG面试题:24个RAG八股文。偷偷背下来,毒打面试官 !
|
机器学习/深度学习 自然语言处理 算法
人类偏好对齐训练技术解析
大型语言模型(LLMs)通过在大量文本数据集上进行无监督预训练,获得丰富的语言模式和知识,这一阶段训练后的模型被称为base model。
|
存储 缓存 安全
ConcurrentHashMap的实现原理,非常详细,一文吃透!
本文详细解析了ConcurrentHashMap的实现原理,深入探讨了分段锁、CAS操作和红黑树等关键技术,帮助全面理解ConcurrentHashMap的并发机制。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
ConcurrentHashMap的实现原理,非常详细,一文吃透!
|
Java 物联网 程序员
还在纠结抽象类和接口?看这篇就够了!
本文从一位程序员的角度出发,讲述了其小学弟在Java开发面试中遇到的难题——抽象类与接口的区别。文章不仅详细解析了两者的定义、特点及主要差异,还提供了实际开发中的应用场景和面试答题技巧,帮助读者更好地理解和应用这一重要知识点。
1684 12
|
域名解析 缓存 网络协议
浏览器输入 URL 回车后会经历哪些步骤?
本文首发于微信公众号“前端徐徐”,详细解析了从在浏览器中输入URL到页面完全呈现的全过程,涵盖检查缓存、URL解析、DNS解析、TCP连接、HTTP请求、服务器响应、浏览器处理响应、页面解析与渲染、关闭TCP连接等关键步骤。通过这些步骤,帮助读者深入了解互联网的工作原理,提升网站性能和用户体验。
333 0
|
缓存 网络协议 Linux
深入探索Linux操作系统的内核优化策略####
本文旨在探讨Linux操作系统内核的优化方法,通过分析当前主流的几种内核优化技术,结合具体案例,阐述如何有效提升系统性能与稳定性。文章首先概述了Linux内核的基本结构,随后详细解析了内核优化的必要性及常用手段,包括编译优化、内核参数调整、内存管理优化等,最后通过实例展示了这些优化技巧在实际场景中的应用效果,为读者提供了一套实用的Linux内核优化指南。 ####
482 1
|
存储 人工智能 安全
操作系统的心脏——内核深度解析
【10月更文挑战第29天】 本文深入探讨了操作系统的核心组件——内核,包括其定义、功能、架构以及在现代计算中的重要性。通过对比不同操作系统内核的设计哲学和技术实现,揭示了内核如何影响系统性能、稳定性和安全性。此外,文章还讨论了未来内核技术的潜在发展方向,为读者提供了一个全面了解内核工作原理的平台。
|
缓存 JavaScript 数据库
手把手教你搭建私有化npm
手把手教你搭建私有化npm
682 2
|
存储 NoSQL 关系型数据库
向量数据库有什么用?
向量数据库是一种特殊类型的数据库,它可以将非结构化数据映射为高维向量,并计算数据之间的相似性。它可以用于查找相似的数据、推荐系统、异常检测和临时存储等应用。目前市场上有一些专门的向量数据库产品,同时也可以使用已有的数据库产品来构建向量数据库。向量数据库的发展前景还不确定,但它已经成为热门技术,并吸引了大量的投资。
|
SQL 存储 关系型数据库
SQL优化万能公式:5 大步骤 + 10 个案例
SQL优化万能公式:5 大步骤 + 10 个案例
4551 7
SQL优化万能公式:5 大步骤 + 10 个案例