首选算法的智慧之光：滑动窗口主题(1)

专栏：算法的魔法世界。

个人主页：手握风云。

目录。

一、滑动窗户。

二、例题讲解。

2.1. 子数组长度最小。

2.2. 无重复字符的最长子串。

2.3. 水果成篮。

2.4. 将 x 减到 0 最小操作。

一、滑动窗户。

        滑动窗算法又称“同向双指针算法”，核心是维护窗口，可根据需要动态调整窗口左右边界。窗户的大小通常取决于当前窗户中的元素是否符合某些条件。通过移动窗口的左右边界，满足条件的子数组或子串可以在一次遍历中找到。

二、例题讲解。

2.1. 子数组长度最小。

       问题要求找出长度最小的子数组，子数组的和大于等于目标值。暴力枚举策略，找出所有和大于等于目标值的子数组，我们需要找出子数组的左右区间，还有一次子数组求和，时间复杂度为。。

       接下来，优化暴力枚举。题目中给出了条件，数组中的元素都是正整数。我们可以定义两个指针left和right，让right向右移动󿀌left和right可以形成一个子数组。当子数组的和大于或等于目标值时，它将被固定，让left指针也向右移动。因为数组是单调的，两个指针不需要回来，可以省去很多不必要的枚举，让子数组中的元素不断进出，维护和更新子数组的和。我们只操作right和left的移动，时间复杂度为。。

代码实现：

class Solution{     public int minSubArrayLen(int target,int[] nums){         int sum = 0,len = Integer.MAX_VALUE,        for(int left = 0,right = 0; right < nums.length; right++){             sum += nums[right];//进窗口            while(sum >= target){                 len = Math.min(len,right-left+1);                sum -= nums[left++];            }        }        return len == Integer.MAX_VALUE ? 0 : len;//如果给定的数组小于目标值，直接返回0    }}。 0 : len;//如果给定的数组小于目标值，直接返回0    }}。

2.2. 无重复字符的最长子串。

       第一个解决方案，使用暴力枚举󿀌也就是说，找出所有不含重复字符的子串，再次比较长度大小。那我们怎么知道字符重复出现࿱呢？f;这里可以使用哈希表，两个指针left和right&xff0也被定义c;让right把遍历过的字符扔进哈希表，此时，我们需要经历两次子串，时间复杂度为。。

       right遇到重复字符时，向右移动left。根据暴力枚举的策略，right还需要回来󿀌再次向右移动󿀌没必要。因为left和right之间有与right指向相同的字符，此时left指针可以直接跳过。因为两个指针也是同向移动的，滑动窗可以用来解决。

       滑动窗口的解决过程是“进窗口”→判断→出窗口→更新结果”。“进入窗口”是将字符扔进哈希表；“判断”的过程是查看哈希表中是否有重复字符；“出窗口”是从哈希表中删除重复的字符。

        实现完整代码：

class Solution{     public int lengthOfLongestSubstring(String s){         char[] str = s.toCharArray();///将字符串转化为字符数组        int hash = new int[128];///用数组模拟哈希表        int left = 0,right = 0,n = s.length;        int ret = 0;        while(right < n){           hash[ss[right]]++;///进入窗口          while (hash[ss[right]] > 1){ ///判断              hash[ss[left++]]--;//出窗口          }          ret = Math.max(ret,right-left+1);///更新结果          right++;///让下一个字符进入窗口        }        return ret;    }}。

2.3. 水果成篮。

2.3. 水果成篮。

        在标题中，我们只有两个篮子，每个篮子只能装一种水果，可以从任何一棵树开始，中间不能越过一棵树󿀌最大数量的水果被收集。让我们来看看下面的测试用例，我们可以采摘[0，1]两棵树󿀌三棵树也可采摘[1、2、2]。也就是说，主题要求我们找到给定数组的最长子数组，子数组中只有两个数字。

        如何知道子数组里只有两种水果，水果的种类和数量可以用哈希表来储存。我们拿出一个段子数组，kinds里面的水果种类恰好是2，此时，让left向右移动�#xff1会有两个结果a;kinds不变，Right不需要向右移动；kinds减少，right向右移动，再次将子数组中的水果种类增加到2。

        通过以上示例分析，我们可以得出双指针是通向移动的，还是用滑动窗来解决问题。“进窗口”，把水果扔进哈希表里。“判断”󿀌当哈希表长度大于2时࿰时c;所以这个窗口不是合法的，要让left向右移动。但是我们不知道left需要移动到哪里，那么我们的哈希表不能只定义一个元素类型，还有一个元素的数量。然后“出窗口”，删除哈希表中的元素，让窗户合法。

        实现完整代码：

class Solution { public int totalFruit(int[] fruits) { Map<Integer,Integer> hash = new HashMap<>();////统计窗口中的水果种类 int ret = 0; for (int left = 0,right = 0;right < fruits.length;right++){ int in = fruits[right]; hash.put(in,hash.getOrDefault(in,0)+1);//进窗口 while(hash.size() > 2){ int out = fruits[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; }}。

2.4. 将 x 减到 0 最小操作数。

2.4. 将 x 减到 0 最小操作数。

        对于上述测试用例，我们可以删除“1”、1、三、#xff0c;此时操作数为3次；我们也可以删除“3”、二、#xff0c;此时最小操作数为2。如果我们直接认为这个问题会很困难c;因为我们不知道是先删左边还是先闪右边。假如我们反过来思考，从数组中找出最长的子数组，最长子数组和target是给定数组和sum减去x的值。

        先定义两个指针left和right&xff0c;right指针移动到下标时，如果right再向右移动一个࿰，子数组和小于sum的子数组c;此时恰好target大于等于sum。然后让left指针向右移动󿀌在这个时候，我们需要考虑，Right需要返回吗？#xff1f;不需要（如下图所示，#xff09;，right要么不动༌或者向右移动󿀌此时符合同向双指针的解决方案，也就是说，滑动窗可以使用。

        “进窗口”，right指针向右移动c;计算子数组和；“判断”，当子数组和大于target时（这里不写等于󿀌为防止代码书写混乱），left指针向左移动c;完成“出窗”操作；最终更新结果󿀌找到最长的子数组。

        实现完整代码：class Solution { public int minOperations(int[] nums, int x) { int sum = 0,len = nums.length; for (int i = 0; i < len; i++) { sum += nums[i]; }//总数组的和 int target = sum - x; if(target < 0) return -1; int ret = -1; for (int left = 0,right = 0,tmp = 0;right < len;right++){ tmp += nums[right];//进窗口 while(tmp > target)//判断 tmp -= nums[left++];//出窗口 if(tmp == target) ret = Math.max(ret,right - left + 1);///更新结果 } if(ret == -1) return ret; else return len - ret; }}。