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

[Leetcode]76.MinimumWindowSubstring最小外壳盖子串-Java

时间:2023-04-01 20:28:49 Java

问题给定两个长度分别为m和n的字符串s和t,返回s的最小窗口子串,使得t中的每个字符(包括重复字符)都包含在窗口中。如果没有这样的子字符串,则返回空字符串“”。将生成测试用例,使得答案是唯一的。子字符串是字符串中连续的字符序列。示例1:输入:s="ADOBECODEBANC",t="ABC"输出:"BANC"解释:最小窗口子串"BANC"包括来自字符串t的'A'、'B'和'C'。示例2:输入:s="a",t="a"输出:"a"解释:整个字符串s是最小窗口。例3:输入:s="a",t="aa"输出:""解释:来自t的两个'a都必须包含在窗口中.由于s的最大窗口只有一个'a',返回空串。约束条件:m==s.lengthn==t.length1<=m,n<=105sandt由大小写英文组成h个字母。跟进:你能找到一个运行时间为O(m+n)的算法吗?提示#1使用两个指针在S中创建一个字母窗口,其中将包含T中的所有字符。隐藏提示#2由于您必须找到S中包含T中所有字符的最小窗口,因此您需要扩展并使用两个指针收缩窗口并继续检查窗口中的所有字符。这种方法也称为滑动窗口方法。L------------------------R,假设这是包含TL--的所有字符的窗口---------------R,这是收缩的窗口。我们发现了一个较小的窗口,其中仍然包含T中的所有字符,当窗口不再有效时,使用右指针再次开始扩展。O(m+n)的时间复杂度解决了,那么BruteForce是行不通的,那么问题来了,如何把嵌套循环优化成一次遍历呢?这时候,就到了滑动窗口算法登场的时候了。该算法适用于解决字符串/数组的子元素问题,可用于降低时间复杂度。抽象来说,整个字符串就像一个长长的滑动窗口,这个窗口中间有两个可移动的玻璃窗口,我们可以这样做:从左端向右端移动一个窗口(右窗口),并满足一定的conditions,暂停移动右窗口,左窗口从左端移动到右端。满足一定条件后,暂停移动左边的窗口,重复上述步骤,直到两个窗口都向右移动,回到本题。s是我们需要遍历的滑动窗口。右窗口的移动遍历s中的字符。右窗口暂停的条件是t中的所有字符都出现了。随着左窗口的移动,s中的字符被丢弃。当t中的字符被丢弃时,左窗口暂停。继续移动到右边的窗口。解题的关键是对字符串t进行建模,在遍历s时用数组或者Map表示t中的字符和出现的次数,当出现t中的字符时,上述数组或者Map的元素值为-1,当计算出的元素的值仍然大于等于0时,表示有效计数使用计数器cnt来表示t中的字符在s中出现的有效次数。当cnt==t.length时,表示t中的所有字符都出现了。t中的所有字符都出现后,开始向左移动WindowreferenceanswerpublicStringminWindow(Strings,Stringt){//128个ASCII字符int[]charCnt=newint[128];int左=0;intfoundCharCnt=0;intminLeft=-1;intminLen=Integer.MAX_VALUE;//当char出现在t中时,循环t,charCnt++for(charc:t.toCharArray()){++charCnt[c];}//循环sfor(intright=0;right=0)中时foundCharCnt++if(--charCnt[s.charAt(right)]>=0){foundCharCnt++;}//当找到t中的所有字符时(foundCharCnt==t.length())while(foundCharCnt==t.length()){//记录minLenandminLeftif(minLen>right-left+1){minLen=right-left+1;minLeft=左;}//如果指针左边的字符在t(++charCnt>0)中,foundCharCnt--if(++charCnt[s.charAt(left)]>0){foundCharCnt--;}//收缩左指针left++;}}返回minLeft==-1?"":s.substring(minLeft,minLeft+minLen);}拓训练给定一个大小为“n”的整数数组。我们的目标是计算数组中“k”个连续元素的最大总和。输入:arr[]={100,200,300,400}k=2Output:700Input:arr[]={1,4,2,10,23,3,1,0,20}k=4Output:39我们通过添加大小为4的子数组{4,2,10,23}得到最大和.Input:arr[]={2,3}k=3Output:InvalidThereisnosubarrayofsize3assizeofwholearrayis2.详细解答参考下方链接链接资料链继续原题https://leetcode.com/problems...滑动窗口算法https://levelup.gitconnected...展开训练答案https://www.geeksforgeeks.org...