我要成为算法高手-滑动窗口篇

滑动窗口算法

滑动窗口的本质还是双指针，只不过滑动窗口的双指针，是同向双指针，两个指针并不回退，都是向同一个方向移动，如果发现两个指针都可以做到不回退，此时可以使用滑动窗口解决问题。

滑动窗口一般的套路就是：进窗口，判断，根据判断结果来决定是否出窗口，另外是更新结果，更新结果的时机不是固定的，要因题而论。

题目1:长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

思路1：暴力解法，枚举出所有的子数组，找出一下长度最小且满足条件的数组

思路1的实现：定义left、right，两层for循环，定义变量sum统计子数组的和，下面是伪代码

int len = Integer.MAX_VALUE;
for(int left =0;left<nums.length;left++){for(int right =left;right<nums.length;right++){sum+=nms[right];if(sum>=target){check(len,right-left+1);//如果len<right-left+1,更新len的值}}
}
return len;

分析暴力解法，可以发现两个问题：当sum满足target要求时，right可以停止往后枚举了，因为right就算往后枚举，sum的要求仍然满足，并且子数组的长度是增加的，并不符合长度最小这个要求；另一个问题是，当枚举完一个符合要求的子数组后，left是往后移动一位，但是，right是否有必要再回到left这个位置？如果right回退，我们又要重新计算sum，但是在枚举上一种情况时，我们已经计算过和了，并不需要重新再计算一次，只需要把left位置的值减去即可。所以我们得出结论，left和right两个“指针”都只需要往同一个方向移动即可，这也就引出今天的主角：滑动窗口

思路2：滑动窗口，定义两个指针left、right，维护窗口边界。进窗口操作：sum+=num[right]，进窗口之后，判断sum的值是否满足条件，如果满足，此时需要更新len的结果，更新之后出窗口。注意：判断操作是循环的，因为出窗口之后，sum可能还是>=target，需要继续出窗口。

代码实现：

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0,right=0;int sum = 0;int len = Integer.MAX_VALUE;while(right<nums.length){//进窗口:sum+=nums[right];//判断,需要循环判断,因为left向后移动之后,sum也有可能还>=targetwhile(sum>=target){//满足条件,更新结果len = Math.min(len,right-left+1);//出窗口            sum-=nums[left];left++;}right++;}if(len==Integer.MAX_VALUE){return 0;}return len;}
}

题目2:无重复字符的最长子串

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

思路1：暴力枚举+哈希表：暴力枚举所有的子串，利用哈希表判断子串中是否有重复字符。

思路1的实现：定义left、right，两层for循环枚举出全部的子串，分别判断每个子串是否满足条件，下面是伪代码

for(int left=0;left<nums.length();left++){for(int right=left;left<nums.length();right++){char ch = s.charAt(right);if(!hash.contains(ch)){hash.put(ch);} else{//统计.....结果break;}}
}

分析暴力解法，right位置出现重复字符时,left+1，right继续回退到left位置，但其实right并不需要回退，同样的，两个指针都是同一个方向移动，我们可以使用滑动窗口

思路2：滑动窗口，进窗口的操作是：把字符扔进哈希表，判断字符是否在哈希表中已经存在过，如果已经存在，需要出窗口，出窗口之后更新结果

代码实现：

class Solution {public int lengthOfLongestSubstring(String s) {char[] chars = s.toCharArray();int[] hash = new int[128];int left = 0;int right = 0;int len = 0;while(right<s.length()){//进窗口hash[chars[right]]++;while(hash[chars[right]]>1) {//说明出现重复字符了,出窗口hash[chars[left]]--;left++;}//更新结果len = Math.max(len,right-left+1);right++;}return len;}
}

题目3:最大连续1的个数

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

问题转换:找出最长的子数组,0的个数不超过k个

思路1：暴力解法+计数器，枚举出所有的子数组，计数器的作用是统计0的个数，

思路1的实现：伪代码如下

int len = 0;
for(int left=0;left<nums.length;left++){int count = 0;for(int right=left;left<nums.length){if(nums[right]==0){count++;}if(count>k){//更新lenbreak;}}
}

分析暴力解法：枚举过程中，right其实没有必要回退到left位置，因为在上一趟遍历中我们已经统计过个数，在下一趟遍历的时候我们只需要根据left的位置是否为0来修改count的值，因此，两个指针都不用回退，可以使用滑动窗口的思想

思路2：滑动窗口，进窗口操作就是统计0的个数，接着判断个数是否大于k，如果大于k需要出窗口，出完窗口之后，才更新结果，因为出窗口后，k的个数才满足要求。

代码实现：

class Solution {public int longestOnes(int[] nums, int k) {int count = 0;int left = 0, right = 0;int len = 0;while (right < nums.length) {// 进窗口if (nums[right] == 0) {count++;}// 判断while (count > k) {// 需要出窗口if (nums[left] == 0) {count--;}left++;}// 更新结果len = Math.max(len, right - left + 1);right++;}return len;}
}

题目4:将x减到0的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

分析题目要求：

如图：题目要我们返回的值是a+b，长度为a的子数组与长度为b的子数组元素之和恰好为x，并且a+b的值是最小的，正难则反，我们可以先求出n-(a+b)。

问题转换：求出最长的子数组的长度len，子数组满足：元素之和恰好为sum-x（sum为原数组nums的元素之和），求出这个长度值之后，直接返回n-len即可

思路1：暴力解法，枚举出所有的子数组，求出满足条件的长度最长的子数组即可

思路1的实现：伪代码如下：

int len = 0;
int curSum = 0;
for(int left =0;left<nums.length;left++){for(int right=left;right<nums.length;right++){if(curSum==sum-x){//更新lenbreak;}}
}
return n-len;

思路2：滑动窗口

class Solution {public int minOperations(int[] nums, int x) {int sum = 0;for (int i : nums) {sum += i;}int len = -1;int n = nums.length;int target = sum - x;int left = 0, right = 0;int curSum = 0;while (right < n) {// 进窗口curSum += nums[right];while (curSum > target && left < n) {//left可能越界                // 如果curSum>target,需要出窗口curSum -= nums[left];left++;}// 出完窗口之后,此时的结果才可能是正确的,// 更新结果if (curSum == target) {len = Math.max(len, right - left + 1);}right++;}if (len == -1) {return -1;}return n - len;}
}

题目5:水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

问题转换：求最长的子数组的长度，子数组满足：水果的种类<=2

思路1：暴力解法+哈希表，暴力枚举出所有的子数组，借助哈希表、计数器来判断水果种类是否超过2

思路2：滑动窗口+哈希表
代码实现：

class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;int[] hash = new int[n + 1];// 构建哈希表int left = 0, right = 0;int count = 0;int len = 0;while (right < n) {// 进窗口if (hash[fruits[right]] == 0) {count++;}hash[fruits[right]]++;while (count > 2) {// 出窗口hash[fruits[left]]--;if (hash[fruits[left]] == 0) {count--;//移出哈希表}left++;}// 更新结果len = Math.max(len, right - left + 1);right++;}return len;}
}

题目6:找到字符串中所有的字母异位词

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

思路1：暴力解法，先把p字符串的词频（字符出现的个数）丢进哈希表中，接着枚举字符串s，枚举出所有长度为len(字符串p的长度)的子串，每枚举一个子串就把该子串丢进一个哈希表中，比较两个哈希表对应字符的频次

思路2：滑动窗口+哈希表，进窗口的操作：把字符扔进哈希表中，何时出窗口?当right位置和left位置长度大于p字符串的长度，此时要出窗口，因为这道题的窗口大小是固定的，窗口大小就是p字符串的长度，出完窗口后，比较两个哈希表的内容，如果内容相同，就把结果扔进集合中
代码实现：

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> ret = new ArrayList<>();int[] hash1 = new int[26];int[] hash2 = new int[26];//把p的字符频次扔进哈希表hash2中for (int i = 0; i < p.length(); i++) {char ch = p.charAt(i);hash2[ch - 'a']++;}//滑动窗口int left = 0, right = 0;while (right < s.length()) {//进窗口char in = s.charAt(right);hash1[in-'a']++;//判断if (right - left + 1 > p.length()) {//出窗口char out = s.charAt(left);hash1[out-'a']--;left++;}//更新结果//比较两个哈希表boolean flg = true;for (int i = 0; i < 26; i++) {if (hash1[i] != hash2[i]) {//两个哈希表内容不同,不是想要的结果flg = false;}}if (flg) {ret.add(left);}right++;}return ret;        }
}

优化：更新结果这里，比较两个哈希表需要遍历一遍哈希表，通过一个变量count，可以优化这个操作，count表示的是有效字符的个数，什么是有效字符？也就是p字符串出现过的字符

核心逻辑：

//进窗口操作
//.....//进窗口后
if(hash1[in]<=hash2[in]){count++;
}//.....//出窗口前
if(hash1[in]<=hash2[in]){count--;
}//出窗口

in和out表示要进窗口、出窗口的字符

代码实现：

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> ret = new ArrayList<>();//哈希表长度26->题目说明了只有小写字母int[] hash1 = new int[26];int[] hash2 = new int[26];//p的哈希表for (int i = 0; i < p.length(); i++) {char ch = p.charAt(i);hash2[ch - 'a']++;//a->0,b->1,c->2.........}//双指针int left = 0, right = 0;int count = 0;//统计窗口中有效字符的个数while (right < s.length()) {//进窗口char in = s.charAt(right);hash1[in - 'a']++;if (hash1[in - 'a'] <= hash2[in - 'a']) {count++;}//判断if (right - left + 1 > p.length()) {//需要出窗口char out = s.charAt(left);if (hash1[out - 'a'] <= hash2[out - 'a']) {count--;}hash1[out - 'a']--;left++;}if (count == p.length()) {ret.add(left);}right++;}return ret;}
}

题目7:串联所有单词的子串

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）

思路：滑动窗口+哈希表

这道题的思路和上一道题"找到字符串中所有的字母异位词"其实是一样的，为什么？

如果把字符串看成一个字母，如图，是不是就变成了找到字符串中所有的字母异位词这个问题？

不同点：

1、哈希表：创建的哈希表是<String,Integer>类型的

2、left和right指针的移动：每次移动len（words中字符串的长度）

3、滑动窗口的执行次数：执行len次

代码实现：

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<>();//1. 把words扔进哈希表中HashMap<String, Integer> hash = new HashMap<>();for (int i = 0; i < words.length; i++) {hash.put(words[i], hash.getOrDefault(words[i], 0) + 1);}int len = words[0].length();//执行len次滑动窗口for (int i = 0; i < len; i++) {int left = i, right = i;int count = 0;//有效字符串的个数HashMap<String, Integer> hashMap = new HashMap<>();//滑动窗口while (right + len <= s.length()) {//进窗口+维护countString in = s.substring(right, right + len);hashMap.put(in, hashMap.getOrDefault(in, 0) + 1);if (hashMap.get(in) <= hash.getOrDefault(in, 0)) {count++;}//判断while ((right - left + 1) > len * words.length) {//需要出窗口+维护countString out = s.substring(left, left + len);if (hashMap.get(out) <= hash.getOrDefault(out, 0)) {count--;}hashMap.put(out, hashMap.get(out) - 1);left += len;}if (count == words.length) {ret.add(left);}right += len;}}return ret;        }
}

题目8:最小覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

解法：滑动窗口+哈希表，进窗口的操作就是让left位置的字符进入哈希表，在进窗口之后维护kinds(字符种类个数)，当两个哈希表中有效字符的种类相等时，此时要出窗口，出窗口之前维护kinds
代码实现：

class Solution {public String minWindow(String ss, String tt) {// 数组模拟哈希表int[] hash1 = new int[128];int[] hash2 = new int[128];// 保存t的频次char[] s = ss.toCharArray();char[] t = tt.toCharArray();int count = 0;// t字符串中字符种类个数// 保存t的频次for (char ch : t) {if (hash2[ch] == 0) {count++;}hash2[ch]++;}// 滑动窗口启动int left = 0, right = 0, kinds = 0;int minLen = Integer.MAX_VALUE, begin = -1;while (right < s.length) {// 进窗口+维护kindschar in = s[right];hash1[in]++;// 维护有效字符种类if (hash1[in] == hash2[in]) {kinds++;}// 判断,如果kinds==count,也就是说hash1有效字符种类和hash2一样while (kinds == count) {// 更新结果,起始位置和最短长度if (right - left + 1 < minLen) {minLen = right - left + 1;begin = left;}// 出窗口+维护kindschar out = s[left];// 出之前判断有效字符种类if (hash1[out] == hash2[out]) {kinds--;}//出窗口hash1[out]--;left++;}right++;}if (begin == -1) {return new String();}return ss.substring(begin, begin + minLen);}
}