【Leet Code 】滑动窗口

前言先思考一个问题互动窗口的左右边界也是两个指针也是一前一后一快一慢滑动窗口和同向快慢指针核心区别在哪快慢指针的操作对象仅限于指针指向的两个元素而滑动窗口通常要对窗口内的区间做统计。通常依赖哈希表。239:滑动窗口最大值题目要求给定一个整数数组nums和整数k要求返回窗口大小位k中最大的数核心思路作为初入门滑动窗口我们用暴力解法来实现代码实现intnnums.length;if(n*k0)returnint[0];if(k1)returnnums;for(inti0;in-k1;i){intmaxValnums[i];for(intj1;jk;j){maxValMath.max(maxVal,nums[ij];}res[i]maxVal;}returnres;总结暴力解法注意双层for循环的边界3无重复字符的最长字串题目要求给定一个字符串s要求找出其中不含重复字符的最长字串核心思路用两个指针left和right标识当前窗口[left,right)用一个hashmap记录每个字符最后出现的位置当右指针遇到重复字符时左指针跳到重复字符的下一个位置确保窗口内无重复每次更新窗口长度维护最大值代码实现MapCharacter,IntegermapnewHashMap();intmaxLen0;intleft0;for(intright0;rights.length();right){Charcs.charAt(right);if(map.containsKey(c)){leftMath.max(left,map.get(c)1);}map.put(c,right);maxLenMath.max(maxLen,right-left1);}returnmaxLen;总结要掌握本题的本质掌握本题核心思路注意left的更新细节438找到字符串中所有字母异位词题目要求给定两个字符串s与p要求找出s中所有p的异位词的起始索引核心思路滑动窗口计数数组用两个数组pcount和scount记录p和当前窗口的字符出现次数初始窗口长度p.length()窗口左移右边加一个字符左边减一个字符每次判断两个计数数组是否 相等如果相等说明当前窗口是异位词代码实现classSolution{publicListIntegerfindAnagrams(Strings,Stringp){ListIntegerresnewArrayList();if(s.length()p.length())returnres;int[]pCountnewint[26];int[]sCountnewint[26];for(charc:p.toCharArray()){pCount[c-a];}intlenPp.length();for(inti0;is.length();i){sCount[s.charAt(i)-a];if(ilenP){//移除窗口左边字符sCount[s.charAt(i-lenP)-a]--;}if(Arrays.equals(pCount,sCount)){res.add(i-lenP1);}}returnres;}}总结掌握这道题需要掌握本题解法思路判断计数数组中元素是否相等的实现办法注意移除窗口左边元素字符的实现方法牵扯到获得pCount与sCount的统计方法的不同。76最小覆盖字串题目要求给定两个字符串s和t要求在s中找出包含t所有字符的最小子串。如果不存在返回空字符串“”。如果有多个最小字串返回任意一个。核心思路统计t中每个字符出现次数用MapCharacter,Integer右指针right扩展窗口不断加入s[right],更新窗口内字符频率如果当前窗口满足条件左指针left收缩窗口尽量缩小窗口同时仍然包含t更新最小长度和起始索引继续移动right知道遍历完整个s代码实现209长度最小的子数组219存在重复元素2