前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >给定m个不重复的字符 [a,b,c,d],以及一个长度为n的字符串tbcacbdata滑动窗口

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

作者头像
翎野君
发布2023-05-12 20:26:49
2580
发布2023-05-12 20:26:49
举报
文章被收录于专栏:翎野君翎野君

题目

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

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

滑动窗口算法

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

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

代码语言:javascript
复制
[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]

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

代码

代码语言:javascript
复制
/**
     * 给定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;
    }

首发链接:https://cloud.tencent.com/developer/article/2285728

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2022-02-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 滑动窗口算法
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档