滑动窗口算法框架（Java版）秒杀力扣题（76、567、438、3、485）

悠悠 2023-01-13 05:48 69阅读 0赞

# 一、声明 #

1.非常感谢东哥（`labuladong`）分享了\*\*[滑动窗口算法框架][Link 1]\*\*；  
2.我在理解了东哥的思想后，用Java实现了滑动窗口算法框架，一来方便自己学习，二来方便一些Java小伙伴；  
3.再次感谢互联网上的大佬们分享智慧结晶。

# 二、滑动窗口算法框架 #

滑动窗口：\[left, right)

Map<Character, Integer> window = new HashMap<>();
    int size = s.size();
    int left = 0, right = 0;
    while(right < size) {
        
    	//增大窗口
    	char c = s.charAt(right);
    	right++;
    	window.put(c, window.getOrDefault(c, 0) + 1);
    
    	while(window needs shrink) {
        
    		//缩小窗口
    		char d = s.charAt(left);
    		left++;
    		window.put(d, window.get(d) - 1);
    	}
    }

> 要熟练使用上述框架，需要做到以下几点：  
> ①适用于子串问题；  
> ②**什么时候缩小窗口取决于题意**；  
> 比如：题目要求子串不得有重复字符。那么当窗口扩大到包含重复字符时，就需要收缩窗口了。（见`三、4`）  
> ③**什么时候计算窗口大小（往往窗口大小就是答案）**；  
> 在window满足题目条件时，就可以计算窗口大小了，即`res = right - left；`；当然了，题目往往要求最优解，所以要更新`res`，寻求最优解。  
> ④最好增加个预判：`if(sizeS < sizeT) return res;`，见`三、3`；

# 三、秒杀力扣题 #

## 0、前言 ##

学习算法框架，就像学习咏春拳，切不可被拳法束缚住，而应该见招拆招。  
而要想见招拆招，只能不断熟练拳法，毕竟孰能生巧嘛。

## 1、[76. 最小覆盖子串][76.] ##

class Solution {
        
        public String minWindow(String s, String t) {
        
            // 需要包含t中的所有字符
            Map<Character, Integer> need = new HashMap<>();
            for(char c : t.toCharArray())
                need.put(c, need.getOrDefault(c, 0) + 1);
    
            //滑动窗口
            Map<Character, Integer> window = new HashMap<>();
    
            /*[left, right) 窗口大小：right - left; */
            int left = 0, right = 0; //初始时，窗口不包含任何元素
            int valid = 0;   //字符找齐了，valid++；
            int size = s.length();
            int minLen = size + 1; //包含t的子串不止1个，要求最小的。
            int start = 0;  //最优解的起点；
            while(right < size) {
        
                /* 右移动right，扩大窗口，寻找可行解 */
                char c = s.charAt(right);
                right++;
                if(need.containsKey(c)) {
        
                    //如果是t中的字符，加入到window中
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if(window.get(c).equals(need.get(c)))
                        valid++;
                }
    
                /* 找到可行解后，右移动left，缩小窗口，进行优化 */
                int needSize = need.size();
                while(valid == needSize) {
        
                    // 不断右移动left，直到valid != needSize
                    c = s.charAt(left);
                    left++;
                    if(need.containsKey(c)) {
        
                        if(window.get(c).equals(need.get(c)))
                            valid--;
                        window.put(c, window.get(c) - 1);
                    }
                    /* 求最优解 [left - 1, right) */ 
                    if(valid != needSize) {
        
                        if(right - left + 1 < minLen) {
        
                            start = left - 1;
                            minLen = right - left + 1;
                        }
                    }
                }
            }
            return minLen == size + 1 ? "" : s.substring(start, start + minLen);
        }
    }

> 注意：`window.get(c).equals(need.get(c))`，千万不能写成`window.get(c) == need.get(c)`!!!

## 2、[567. 字符串的排列][567.] ##

class Solution {
        
        public boolean checkInclusion(String s1, String s2) {
        
            Map<Character, Integer> need = new HashMap<>();
            for(char c : s1.toCharArray())
                need.put(c, need.getOrDefault(c, 0) + 1);
            Map<Character, Integer> window = new HashMap<>();
            int valid = 0;
            int left = 0, right = 0;
            int size1 = s2.length();
            while(right < size1) {
        
                char c = s2.charAt(right);
                right++;
                if(need.containsKey(c)) {
        
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if(window.get(c).equals(need.get(c)))
                        valid++;
                }
                int needSize = need.size();
                int size2 = s1.length();
                while(valid == needSize) {
        
                    if(right - left == size2)
                        return true;
                    c = s2.charAt(left);
                    left++;
                    if(need.containsKey(c)) {
        
                        if(window.get(c).equals(need.get(c)))
                            valid--;
                        window.put(c, window.get(c) - 1);
                    }
                }
            }
            return false;
        }
    }

> 和76的代码基本一致，这就是滑动算法框架的魅力：一个模板秒杀一系列的题目（这实际上属于举一反三，毕竟得先理解题意，然后才知道如何应用模板）。

*  另一种实现方法

class Solution {
        
        public boolean checkInclusion(String s1, String s2) {
        
            /* 运用滑动窗口算法思想*/
            //按照题目意思，此题的滑动窗口是固定大小；
            boolean res = false;
            int size1 = s1.length(), size2 = s2.length();
            int left = 0, right = left + size1;
            /* 对s1先排序 */
            char[] str1 = s1.toCharArray();
            Arrays.sort(str1);
            while(right <= size2) {
        
                char[] tmp = s2.substring(left, right).toCharArray();
                Arrays.sort(tmp);
                if(String.valueOf(tmp).equals(String.valueOf(str1))) {
        
                    res = true;
                    break;
                }
                left++;
                right = left + size1;
            }
            return res;
        }
    }

> 千万不要局限于模板，虽然上述代码性能不如滑动窗口算法框架，但是代码量少且容易实现。

## 3、[438. 找到字符串中所有字母异位词][438.] ##

class Solution {
        
        public List<Integer> findAnagrams(String s, String p) {
        
            List<Integer> res =  new ArrayList<>();
            int sizeS = s.length(), sizeT = p.length(); 
            if(sizeS < sizeT) return res;
            Map<Character, Integer> need = new HashMap<>();
            for(char c : p.toCharArray())
                need.put(c, need.getOrDefault(c, 0) + 1);
            int valid = 0;
            int needSize = need.size();
            Map<Character, Integer> window = new HashMap<>();
            int left = 0, right = 0;
            
            while(right < sizeS) {
        
                char c = s.charAt(right);
                right++;
                if(need.containsKey(c)) {
        
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if(window.get(c).equals(need.get(c)))
                        valid++;
                }
    
                while(valid == needSize) {
        
                    if(right - left == sizeT) {
        
                        res.add(left);
                    }
                    c = s.charAt(left);
                    left++;
                    if(need.containsKey(c)) {
        
                        if(window.get(c).equals(need.get(c)))
                            valid--;
                        window.put(c, window.get(c) - 1);
                    }
                }
            }
            return res;
        }
    }

> 和567代码几乎一样。  
> 另外，新增1个预判：`if(sizeS < sizeT) return res;`

## 4、[3. 无重复字符的最长子串][3.] ##

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            Map<Character, Integer> window = new HashMap<>();
            int left = 0, right = 0;
            int size = s.length();
            int res = 0;
            while(right < size) {
        
                char c = s.charAt(right);
                window.put(c, window.getOrDefault(c, 0) + 1);
                right++;
                while(window.get(c) > 1) {
        
                    /* 一旦出现了重复字符，就需要收缩窗口了 */
                    char d = s.charAt(left);
                    left++;
                    window.put(d, window.get(d) - 1);
                }
                // [left, right) 窗口中没有重复字符
                res = Math.max(res, right - left);
            }
            return res;
        }
    }

> 这题并不能生搬硬套华东算法框架，但仍旧是滑动窗口的思想。

/* 伪代码 */
    while(right < size) {
        
    	①统计字符，扩大窗口;(right++)
    	②一旦重复，缩小窗口;(left++)
    	③更新结果：res = Math.max(res, right - left);
    }

## 5、[485. 最大连续 1 的个数][485. _ 1] ##

class Solution {
        
        public int findMaxConsecutiveOnes(int[] nums) {
        
            int left = 0, right = 0;
            int res = 0;
            while(right < nums.length) {
        
                //扩大窗口
                while(right < nums.length && nums[right] == 1) right++;
                //遇到了0或者已经超出边界，即不能再扩大了；
                res = Math.max(res, right - left);
                //缩小窗口
                right++; //跳过0
                left = right;
            }
            return res;
        }
    }

> 虽然这道题看上去很像滑动窗口的题目，但是这种**简单**题反而用直觉的方法更好（不易出错，毕竟杀鸡焉用牛刀！）  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]

## 6、后言 ##

（1）最好不要奢望无脑套用框架刷算法题，而之所以学习些算法框架（或者说套路）是因为多积累一种解题思路往往多了一些机会去秒杀算法题。  
（2）本文的滑动窗口算法框架在性能方面并不是最优的（毕竟套用框架省了脑力，多半会牺牲性能）。

[Link 1]: https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA
[76.]: https://leetcode-cn.com/problems/minimum-window-substring/
[567.]: https://leetcode-cn.com/problems/permutation-in-string/
[438.]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[485. _ 1]: https://leetcode-cn.com/problems/max-consecutive-ones/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20221022/4a4cd39c09d24a7abbc3d360d052a4de.png