Java力扣---滑动窗口（2）

209. 长度最小的子数组 - 力扣（LeetCode）

分析：这个题目是在滑动窗口题目的类似题目中的，所以最开始就是准备用滑动窗口来做的

这里用到了滑动窗口的先进先出，但是要用数字和sum做更新，所以我想到了队列，但是在做题目的时候，因为不知道队列可以有多长，所以要用left和right来记录队列的开始和结束

注意1：我们只需要直到队列的开始元素和结束元素的下标，并不需要直到中间存储的数据，换句话说，中间的所有数据的下标都是要放在队列之中的，是连续的，所以并不需要队列，只需要记录first和last就好了

注意2：既然用到了left和right，那么就不用使用队列了，在写的代码里，队列是完全没用到的的------所以，写完代码要重新再看一遍，是不是有冗余的部分存在

class Solution { public int minSubArrayLen(int target, int[] nums) { //Deque<Integer> queue = new ArrayDeque<>(); int sum=0; int left=0,right=0; boolean flag=true; int ans=nums.length+1; while(right<nums.length){ while(sum<target && right<nums.length){ //queue.addLast(right); sum+=nums[right]; right++; } while(sum>=target){ flag=false; //queue.removeFirst(); sum-=nums[left]; left++; } ans=Math.min(ans,right-left+1); } if(flag) ans=0; return ans; } }

76. 最小覆盖子串 - 力扣（LeetCode）

分析：这个题是上一题的延申

1.要注意到可能有重复的字母，所以这里要单独分析

2.这里也是滑动窗口，但是并不需要用到队列，这里和上一题是一样的

3.这里只考虑字母出现了没有，并不考虑出现的顺序

--->这个解法很巧的一个思路是用次数,出现了几次来判断，这样子既可以判断有没有包含所有的，又可以巧妙地化解重复字符的问题

4.因为其中涉及到判断是否现在的子串满足条件，这个判断要多次出现，所以可以写成方法

5.这里的一个小巧思就是用字符的ASCII码来做字符的判断，这样就可以用数组了，我最开始想到的是用map来做，但是map会更麻烦很多，要考虑到是否存在，存在了再取出值加一，删除的时候也要取出值-1

class Solution { public String minWindow(String s, String t) { int[] tarr=new int[128]; int[] sarr=new int[128]; String sub=s; for(char c:t.toCharArray()){ tarr[c]++; } boolean flag=true; int left=0,right=0; while(right<s.length()){ while (iscontened(tarr,sarr)) { if(sub.length()> right-left){ sub=s.substring(left,right); } flag=false; sarr[s.charAt(left)]--; left++; } while (!iscontened(tarr,sarr) &&right<s.length()){ sarr[s.charAt(right)]++; right++; } } while (iscontened(tarr,sarr) && left<s.length()) { if(sub.length()> right-left){ sub=s.substring(left,right); } flag=false; sarr[s.charAt(left)]--; left++; } if(flag) return ""; return sub; } public static boolean iscontened(int[] tarr,int[] sarr){ for (int i = 0; i < tarr.length; i++) { if(tarr[i]>sarr[i]){ return false; } } return true; } }

这是用map做的代码，运行时间会高很多

1.contained遍历的时候一定是用tmap遍历的，而且要考虑不存在的情况

2.在存放的时候，要分开考虑已经有的键和还没有的键

class Solution { public String minWindow(String s, String t) { Map<Character, Integer> tmap = new HashMap<>(); Map<Character, Integer> smap = new HashMap<>(); String sub=s; for(char c:t.toCharArray()){ if(tmap.containsKey(c)){ tmap.put(c,tmap.get(c)+1); }else{ tmap.put(c,1); } } boolean flag=true; int left=0,right=0; char c; while(right<s.length()){ while (iscontened(tmap,smap)) { if(sub.length()> right-left){ sub=s.substring(left,right); } flag=false; c=s.charAt(left); if(smap.containsKey(c)){smap.put(c,smap.get(c)-1);} left++; } while (!iscontened(tmap,smap) && right<s.length()){ c=s.charAt(right); if(smap.containsKey(c)){smap.put(c,smap.get(c)+1);} else{smap.put(c,1);} right++; } } while (iscontened(tmap,smap) && left<s.length()) { if(sub.length()> right-left){ sub=s.substring(left,right); } flag=false; c=s.charAt(left); if(smap.containsKey(c)){smap.put(c,smap.get(c)-1);} left++; } if(flag) return ""; return sub; } public static boolean iscontened(Map<Character,Integer> tmap,Map<Character,Integer> smap) { for (Map.Entry<Character, Integer> entry : tmap.entrySet()) { if (!smap.containsKey(entry.getKey())) { return false; }else if (entry.getValue() > smap.get(entry.getKey())) { return false; } } return true; } }

代码思路学习灵茶山艾府 - 力扣（LeetCode）