一、题目分析
分析：就是在S中找出包括T的所有字符的最小窗口 ，要求时间复杂度是O(N)
所以有了之前滑动窗口的概念，这个题会好理解一点
值得注意的是
数量足够：就是当前窗口中，begin位置的字符出现至少两次，那么为了达到最小，自然就可以想到要把begin向右移动一位
来自下面博主的文字：
字符串和哈希表的问题。hashmap来存储t字符串中个字母元素的出现次数，left right记录当前子字符串的左右下标值，minminleft minright 变量存储当前子字符串的最小长度以及左右下标。首先从前向后遍历字符串，找到包含t中元素的子字符串，遍历的同时记得更新hashmap中的字母元素次数的个数，每出现一次对应-1,同时count++，在count++的时候要注意： aedbbac 找abc 时， b连续出现过两次，在count++的时候只在b出现的第一次++， 第二次不+，因为我们只需要一个b。然后就是left向后收缩，right向后扩展，left向后收缩也就是left++的一个过程，去掉无用字符，每去掉一个字符的时候要对应判断一下是否是t中元素，将hashmap中的频率更新，以及count--，在count--的时候需要注意，即使当前删减的字符是t中元素，但是它在hashmap中的计数次数是否是>=0， 也就是它是否重复出现比如上一步骤的例子： aedbbac 找abc 时， 显然当left指向第一个b时，hashmap中要更新，但是count不要--。之后就是不断更新min和minleft minright。 --------------------- 作者：Pi_dan 来源： 原文：https://blog.csdn.net/qq_38595487/article/details/80388100
二、java代码
class Solution { public String minWindow(String s, String t) { String string = ""; //hashmap来统计t字符串中各个字母需要出现的次数 HashMap<Character,Integer> map = new HashMap<>(); for (char c : t.toCharArray()) map.put( c, map.containsKey(c) ? map.get(c)+1 : 1); //用来计数 判断当前子字符串中是否包含了t中全部字符 int count = 0; //记录当前子字符串的左右下标值 int left = 0; int right = 0; //记录当前最小子字符串的大小以及第一最后字符的下标值 int min = Integer.MAX_VALUE; int minLeft = 0; int minRight = 0; for (; right < s.length() ; right++) { char temp = s.charAt(right); if (map.containsKey(temp)){//向后遍历出所包含t的字符串 count = map.get(temp) > 0 ? count+1 : count; map.put(temp,map.get(temp)-1); } while (count == t.length()){//得出一个符合条件的子字符串 if (right-left < min){//更新min minLeft minRight 信息 min = right - left; minLeft = left; minRight = right; } char c = s.charAt(left); if (map.containsKey(c)){//向左收缩 判断所删减的字符是否在map中 if (map.get(c) >= 0)count --;//count--时需要判断一下是否需要-- map.put(c,map.get(c)+1); } left++; } } return min == Integer.MAX_VALUE ? "" : s.substring(minLeft,minRight+1); } }
