当前位置: 首页 > 后端技术 > Java

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

时间:2023-04-01 13:58:43 Java

title给定m个非重复字符[a,b,c,d]和一个字符串tbcacbdatawith一个长度为n,问能否在这个字符串中找到一个长度为m的连续子串,使得这个子串正好由上面m个字符组成,顺序无所谓,返回任意一个满足条件的起始子串的位置,如果没有找到,返回-1。例如,在上面的示例中,返回3。本题子串需要满足m的长度,字符不重复。可以使用一个长度为m的滑动窗口来遍历字符串。窗口中的每个字符必须出现一次。如果满足条件,则返回到窗口的起始位置。滑动窗口算法滑动问题涉及滑动窗口,它是一个在大数组上运行的子列表,大数组是元素的底层集合。假设有一个数组[abcdefgh],一个大小为3的滑动窗口在其上滑动,则有:[abc][bcd][cde][def][efg][fgh]一般在数组在合法范围内滑动,同时动态记录一些有用的数据,在很多情况下可以大大提高算法的效率。代码/***给定m个非重复字符[a,b,c,d],和一个长度为n的字符串tbcacbdata,*能否在这个字符串中找到长度为m的连续子串,使得这个子串刚好组成以上m个字符。*顺序无所谓,返回任意一个满足条件的子串的起始位置,没有找到则返回-1。比如上面的例子,acbd,3.**@paramch*@params*@return*/privateintfindIndex(char[]ch,Strings){inttargetCharSize=ch.length;inttotalCharSize=s.length();如果(targetCharSize>totalCharSize){返回-1;}for(inti=0;i