给定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;
    }


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


目录
相关文章
|
5月前
|
算法
【算法】滑动窗口——无重复字符的最长子串
【算法】滑动窗口——无重复字符的最长子串
|
5月前
|
Java
输入一个字符串,找出其中不含有重复字符的最长子串的长度。
这篇文章提供了一个Java解决方案,用于找出输入字符串中不含有重复字符的最长子串的长度,通过使用HashSet来跟踪字符并计算最长不重复字符子串。
输入一个字符串,找出其中不含有重复字符的最长子串的长度。
|
存储 算法
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
82 0
|
8月前
|
算法 测试技术 C#
【map】【滑动窗口】【字典树】C++算法:最长合法子字符串的长度
【map】【滑动窗口】【字典树】C++算法:最长合法子字符串的长度
|
人工智能
最长连续不重复子串
最长连续不重复子串
138 0
最长连续不重复子串
|
Java
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)
125 0
给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现)
|
测试技术
字符串中有多少个不重复的字符并按由前到后的顺序输出一个新的字符串和该字符串长度的整数
字符串中有多少个不重复的字符并按由前到后的顺序输出一个新的字符串和该字符串长度的整数
99 0
滑动窗口__最长不含重复字符的子符串_和为S的连续正整数序列(剑指offer)
滑动窗口__最长不含重复字符的子符串_和为S的连续正整数序列(剑指offer)
114 0
滑动窗口__最长不含重复字符的子符串_和为S的连续正整数序列(剑指offer)
|
Java Python
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度