【Leet Code 】滑动窗口

前言

先思考一个问题：互动窗口的左右边界也是两个指针，也是一前一后一快一慢，滑动窗口和同向快慢指针核心区别在哪？

快慢指针的操作对象仅限于指针指向的两个元素，而滑动窗口通常要对窗口内的区间做统计。通常依赖哈希表。

239:滑动窗口最大值

题目要求：给定一个整数数组nums和整数k
要求：返回窗口大小位k中最大的数

核心思路

作为初入门滑动窗口，我们用暴力解法来实现

代码实现

intn=nums.length;if(n*k=0)returnint[0];if(k=1)returnnums;for(inti=0;i<n-k+1;i++){intmaxVal=nums[i];for(intj=1;j<=k;j++){maxVal=Math.max(maxVal,nums[i+j];}res[i]=maxVal;}returnres;

总结

暴力解法：注意双层for循环的边界

3：无重复字符的最长字串

题目要求：给定一个字符串s
要求：找出其中不含重复字符的最长字串

核心思路

1. 用两个指针left和right标识当前窗口[left,right)
2. 用一个hashmap记录每个字符最后出现的位置
3. 当右指针遇到重复字符时，左指针跳到重复字符的下一个位置，确保窗口内无重复
4. 每次更新窗口长度，维护最大值

代码实现

Map<Character,Integer>map=newHashMap<>();intmaxLen=0;intleft=0;for(intright=0;right<s.length();right++){Charc=s.charAt(right);if(map.containsKey(c)){left=Math.max(left,map.get(c)+1);}map.put(c,right);maxLen=Math.max(maxLen,right-left+1);}returnmaxLen;

总结

要掌握本题的本质：掌握本题核心思路，注意left的更新细节

438：找到字符串中所有字母异位词

题目要求：给定两个字符串s与p
要求：找出s中所有p的异位词的起始索引

核心思路（滑动窗口+计数数组）

1. 用两个数组pcount和scount记录p和当前窗口的字符出现次数
2. 初始窗口长度=p.length()
3. 窗口左移：右边加一个字符，左边减一个字符；每次判断两个计数数组是否 相等；如果相等说明当前窗口是异位词

代码实现

classSolution{publicList<Integer>findAnagrams(Strings,Stringp){List<Integer>res=newArrayList<>();if(s.length()<p.length())returnres;int[]pCount=newint[26];int[]sCount=newint[26];for(charc:p.toCharArray()){pCount[c-'a']++;}intlenP=p.length();for(inti=0;i<s.length();i++){sCount[s.charAt(i)-'a']++;if(i>=lenP){//移除窗口左边字符sCount[s.charAt(i-lenP)-'a']--;}if(Arrays.equals(pCount,sCount)){res.add(i-lenP+1);}}returnres;}}

总结

掌握这道题，需要：掌握本题解法思路；判断计数数组中元素是否相等的实现办法；注意移除窗口左边元素字符的实现方法，牵扯到获得pCount与sCount的统计方法的不同。

76：最小覆盖字串

题目要求：给定两个字符串s和t，
要求：在s中找出包含t所有字符的最小子串。
如果不存在：返回空字符串“”。
如果有多个最小字串，返回任意一个。

核心思路

1. 统计t中每个字符出现次数：用Map<Character,Integer>
2. 右指针right扩展窗口
   不断加入s[right],更新窗口内字符频率
   如果当前窗口满足条件
3. 左指针left收缩窗口
   尽量缩小窗口，同时仍然包含t
   更新最小长度和起始索引
4. 继续移动right，知道遍历完整个s

代码实现

209：长度最小的子数组

219：存在重复元素2