滑动窗口 

      本篇文章中会带大家从零基础到学会利用滑动窗口的思想解决算法题，我从力扣上筛选了三道题，难度由浅到深，会附上题目链接以及算法原理和解题代码，希望大家能坚持看完，绝对能有收获，大家有更好的思路也欢迎大家在评论区交流啊！

         欢迎大家交流！！！

         欢迎大家交流！！！

         欢迎大家交流！！！

文章顺序：

题目链接-》算法原理-》代码呈现

思想总结：

       滑动窗口可以理解为是快慢双指针的一个分支，也是利用双指针一个在前一个在后，通过判断条件使两个指针形成一个大小不断变化的窗口，不断向前移动。滑动窗口的解题思想是在暴力枚举的思想上演化而来的，利用数据的单调性使快指针不用回退，通常能使算法复杂度在暴力枚举的基础上减少一个数量级。

1.长度最小的子数组 

题目链接：

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

算法思想：

• 如果窗⼝内元素之和⼤于等于 target ：更新结果，并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件）
• 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝

代码呈现： 

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
       int left=0;
       int right=0;
       int n=nums.length;
       int sum=0;
       int min=0;
       for(int i=0;i<n;i++){
         sum+=nums[right];
         right++;
         while(true){
             if(sum>=target){
             int a=right-left;
             if(min>a||min==0){
                 min=a;
             }
             sum-=nums[left];
             left++;
            }else{
                break;
            }
         }
       }
       return min;
    }
}

2. 水果成篮

 题目链接：

https://leetcode.cn/problems/fruit-into-baskets/description/

算法思路：

• 如果⼤⼩超过 2：说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗⼝，直到哈希表的大小小于等于 2，然后更新结果；
• 如果没有超过 2，说明当前窗⼝内⽔果的种类不超过两种，直接更新结果 ret。

算法流程：

1. 初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量；
2. 初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0；
3. 当 right ⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
   1. 将当前⽔果放⼊哈希表中；
   2. 判断当前⽔果进来后，哈希表的⼤⼩：

          如果超过 2：

                   -将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；

                   -如果这个元素的频次减⼀之后变成了 0，就把该元素从哈希表中删除；

                   -重复上述两个过程，直到哈希表中的⼤⼩不超过 2；

   3. 更新结果 ret；

   4. right++，让下⼀个元素进⼊窗⼝
4. 循环结束后，ret 存的就是最终结果

代码呈现： 

class Solution {
    public int totalFruit(int[] f) {
        Map<Integer,Integer> hash=new HashMap<>();
        int ret=0;
        for(int left=0,right=0;right<f.length;right++){
            int in=f[right];
            hash.put(in,hash.getOrDefault(in,0)+1);
            while(hash.size()>2){
                int out=f[left];
                hash.put(out,hash.get(out)-1);
                if(hash.get(out)==0){
                    hash.remove(out);
                }
                left++;
            }
            ret=Math.max(ret,right-left+1);
        }
           return ret;
    }
}

 3.找到字符串中所以字母异位词

题目链接：

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

算法思路：

• 因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；
• 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p的异位词；
• 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。

代码呈现： 

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] arr1 = s.toCharArray();
        int n = arr1.length;
        char[] arr2 = p.toCharArray();
        List<Integer> list = new ArrayList<>();
        Map<Character, Integer> hash = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            hash.put(arr2[i], hash.getOrDefault(arr2[i], 0) + 1);
        }
        if (hash.isEmpty()) {
            return list;
        }
        Map<Character, Integer> hash1 = new HashMap<>();
        for (int left = 0, right = 0; right < n; right++) { 
            if (hash.containsKey(arr1[right])) {
                hash1.put(arr1[right], hash1.getOrDefault(arr1[right], 0) + 1);
                while(hash1.get(arr1[right])>hash.get(arr1[right])){
                    hash1.put(arr1[left],hash1.get(arr1[left])-1);
                    left++;
                }
            } else {
                 left=right+1;
                 hash1.clear();
            }
            if (hash.equals(hash1)) {
                list.add(left);
                hash1.put(arr1[left],hash1.get(arr1[left])-1);
                left++;
            }
        }
        return list;
    }
}