长度最小的子数组

解题思路：滑动窗口

不断调节子序列的起始位置和终止位置，从而得出我们想要的结果。滑动窗口归根结底是双指针的问题。

滑动窗口要考虑的问题主要是三个：

窗口内是什么？

如何移动窗口的起始位置？

如何移动窗口的结束位置？

窗口就是 满足其和 >= target 的长度最小的连续子数组

窗口的起始位置如何移动，如果当前窗口的值大于等于target了，窗口就要向前移动了，这里要注意while循环，一直缩小到小于target为止

窗口的终止位置如何移动，窗口的结束位置就是遍历数组的指针，也就是for循环的里的索引。

完整代码如下：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int slow = 0;
        int result = Integer.MAX_VALUE;
        int sum = 0;
        for(int fast = 0; fast < nums.length; fast++){
            sum += nums[fast];
            while(sum >= target){
                sum -= nums[slow];
                result = Math.min(result, fast - slow + 1);
                slow++;
            } 
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

时间复杂度为O(n)

904.水果篮子

解题思路：使用滑动窗口，slow和fast分别表示满足要求的窗口的左右边界，同时使用哈希表存储这个窗口内的数字以及出现的次数。

具体流程：每次将 fast 移动一个位置，并将 fruits[fast] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么就需要不断移动 slow，（具体代码操作为将 fruits[slow] 对应的哈希表的值减 1 后做覆盖操作），然后对 fruit[slow] 判断其值是否为 0，如果是则移除，直到哈希表满足要求为止（while循环）。

完整代码如下：

class Solution {
    public int totalFruit(int[] fruits) {
        int slow = 0;
        Map<Integer, Integer> typeMap = new HashMap<>();
        int result = 0;
        for(int fast = 0; fast < fruits.length; fast++){
            typeMap.put(fruits[fast], typeMap.getOrDefault(fruits[fast], 0) + 1);
            while(typeMap.size() > 2){
                //将slow所指的树减1然后覆盖，覆盖完判断出现次数为0就移除
                typeMap.put(fruits[slow], typeMap.get(fruits[slow]) - 1);
                if(typeMap.get(fruits[slow]) == 0){
                    typeMap.remove(fruits[slow]);
                }
                slow++;
            }
            result = Math.max(result, fast - slow + 1);
        }
        return result;
    }
}

时间复杂度为O(n)

76.最小覆盖子串

解题思路：

在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的r指针，和一个用于「收缩」窗口的l指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在s上滑动窗口，通过移动r指针不断扩张窗口。当窗口包含t全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

关键在于如何判断当前的窗口包含所有t所需的字符呢？

可以用一个哈希表表示t中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含t的哈希表中的所有字符，并且对应的个数都不小于t的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

具体实现：

//记录字符串t中所有不同字母出现的次数
Map<Character, Integer> tMap = new HashMap<>();
//建立滑动窗口中的所有不同字母出现的次数
Map<Character, Integer> sMap = new HashMap<>();

//判断滑动窗口是否为可行窗口
private boolean isWindowValid(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
            char key = entry.getKey();
            int required = entry.getValue();
            
            if (sMap.getOrDefault(key, 0) < required) {
                return false;
            }
        }
        return true;
}

完整代码如下：

class Solution {
    //记录字符串t中所有不同字母出现的次数
    Map<Character, Integer> tMap = new HashMap<>();
    //建立滑动窗口中的所有不同字母出现的次数
    Map<Character, Integer> sMap = new HashMap<>();
    public String minWindow(String s, String t) {
        char[] sCharArray = s.toCharArray();
        char[] tCharArray = t.toCharArray();
        for(int i = 0; i < tCharArray.length; i++){
            tMap.put(tCharArray[i], tMap.getOrDefault(tCharArray[i], 0) + 1);
        }
        int left = 0;
        int right = 0;
        int result = Integer.MAX_VALUE;
        int slow = 0;
        for(int fast = 0; fast < sCharArray.length; fast++){
            sMap.put(sCharArray[fast], sMap.getOrDefault(sCharArray[fast], 0) + 1);
            while(isWindowValid(sMap, tMap)){//滑动窗口处于可行状态
                if(result > fast - slow + 1){
                    left = slow;
                    right = fast;
                    result = fast - slow + 1;
                }
                sMap.put(sCharArray[slow], sMap.get(sCharArray[slow]) - 1);
                if(sMap.get(sCharArray[slow]) == 0){
                    sMap.remove(sCharArray[slow]);
                }
                slow++;
            }
            
        }
        return result == Integer.MAX_VALUE ? "" : s.substring(left, right + 1);
    }

    //判断滑动窗口是否为可行窗口
    private boolean isWindowValid(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
            char key = entry.getKey();
            int required = entry.getValue();
            
            if (sMap.getOrDefault(key, 0) < required) {
                return false;
            }
        }
        return true;
    }
}

时间复杂度为O(n)