滑动窗口算法-力扣题解

首先介绍滑动窗口的定义及三个重要的步骤：1收缩条件、2窗口右移更新 和3窗口左移更新，然后以一个简单的定长求窗口和的例子介绍滑动窗口的思想并给出模板；然后还是5道经典力扣题及详细题解、最后总结。

最后的结论是：“有些时候模板也解决不了问题！” 遇到hard题还是回厕所哭去吧….

[1]参考了开源项目模板 github.com/greyireland/algorithm-pattern
[2]参考了博客园huansay的文章www.cnblogs.com/huansky/p/13488234.html
除文中标注的4处引用外，其他皆为原创，保留权力。

1 定义和模板

1.1 滑动窗口的定义

“滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。”[2]

两个集合的定义：窗口集合指当前窗口，一般只关心窗口中有用的元素，如窗口和、最大值、字符出现的次数等；需求集合就是题目给的条件，用它是否满足判断是否需要收缩。 滑动窗口在使用方面，我把它分为两类：1、窗口长度固定的；2、窗口长度可以根据需要变化的。两种本质是一样的，只是在窗口是否收缩的条件不一样

我觉得最重要的是要弄清楚收缩条件、窗口右移更新 **和窗口左移更新**

• 收缩条件指何时收缩，并且要用程序的语言（计数、长度或者什么）来判断。
  • 定长窗口收缩的条件就是窗口长度>指定长度
  • 不定长窗口就是窗口内的元素满足了某个条件、你收缩一下让他不满足。（当然收缩之前一般要保存一下结果）
• 窗口右移更新：指右指针右移之后，窗口内的数据更新，一般只更新有用的信息
• 窗口左移更新：指左指针右移之后，一般是删除掉原左指针对应的元素信息
  • ==一般结果集的获取也放在收缩循环里面==
  • ==但如果收缩循环没有完成窗口的彻底更新，结果集的获取就不能放在循环里，比如最长子串==

1.2 一个定长窗口的例子

计算长度为k的窗口元素之和，返回一个数组。数组长度为length-k+1、每个元素为对应窗口的和；图片来源于[2]

遍历过程如上图，如果用常规暴力解法，就是两层循环：外层遍历数组，内层遍历窗口中的所有值并加和

for(int i=0;i<nums.length-k;++i){
    int sumWin = 0;
    for(int j=i;j<i+k;j++){
        sumWin += nums[j];
    }
    res[i] = sumWin;
}

但其实内层是不必要重新遍历一次的：我们如果有了前一个窗口的信息（前一个窗口的和），那我们要求下一个窗口的和，只需要将sumWin减去移出窗口的那个值&&加上新增进窗口的那个值。

虽然用for循环也可以，这里还是用模板中常用的while循环；并且如果窗口大小固定，收缩窗口其实不需要循环、用if就够了。

//这里爷用通用的left和right指针来操作窗口的范围和元素
//通用模板是左闭右开区间
int left = 0, right = 0;
int sumWin = 0; int i = 0;
while(right<nums.length){
    //扩大窗口
    int a = nums[right];
    right++;
    //窗口数据更新
    sumWin +=a;
    
    //判断是否需要收缩窗口
    while(right-left>=k){
        //满足条件加入结果集
        if(right-left==k) res[i++]=sumWin;
        //收缩窗口
        left++;
        //窗口数据更新
        sumWin -= nums[left];
    }  
}
return res;

1.3 滑动窗口模板

先放一个[1]开源项目的通用模板。代码中需要变化的地方[1]:

1. 右指针右移之后窗口数据更新
2. 判断窗口是否要收缩，结果集的更新紧跟着判断收缩之后
3. 左指针右移之后窗口数据更新
4. 根据题意计算结果

代码中的变量：

• need和window都是map集合：need存是固定的目标字符串元素（或数组）；window存窗口当前所含的元素。
• match 变量表示窗口中满足 need条件的字符个数，就是匹配次数

/* 滑动窗口算法框架[1] */
void slidingWindow(string s, string t) {
    Map<Character,Integer> window = new HashMap<>();
    Map<Character,Integer> need = new HashMap<>();
    //初始化need集合
    for(int i=0;i<t.length();++i){
        char a = t.charAt(i);
        need.put(a,need.getOrDefault(a,0)+1);
    }

    int left = 0, right = 0;
    int match = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        System.out.println("["+left+","+right+")");
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

等我多做几道题之后，再看看能不能把它改写成 java 版的吧，这里还有一个疑问，为什么要搞成左闭右开[left,right)的区间，左右都闭起来[left,right]不是更符合常识一点么？还有一个就是如果是窗口长度不变，就不需要用while，用if就够了….不过统一用while也不错。

我还有话要讲：

对于一些字符串、数组贮存问题，因为字符串个数、数字个数都是有限的：ASCII字符的个数是128个、数字个数是10个。所以大多数时候need和window可以用桶的思想来贮存字符、显然比Map更快。

使用数组存元素时，字符的值的大小就是数组的下标索引，而字符出现的次数就是该位置应该付的值

2 力扣经典题目及解答

又要开始喜闻乐见的分析题意、和套模板环节了。这跟高考数学物理一般难度的题也没什么区别，就是多做、然后就tmd记住了，遇到差不多的也能写。

2.1 力扣76.最小覆盖子串（困难）

https://leetcode-cn.com/problems/minimum-window-substring/

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 ：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

思路分析

果然是hard级别的题，我上来就分析收缩条件、窗口集合和需求集合：

• 收缩条件，当需求t中的所有字符都出现在窗口中并且出现此处也相同时（完全匹配），需要保存结果并收缩窗口
  • 匹配条件用一个match变量表示，每一次循环right右移一格，判断match是否需要+1
  • 当match达到最大值时，考虑紧缩窗口left–。紧缩窗口时通过判断紧缩之后对match是否有影响来考虑是否对match–
• 窗口集合win用一个hashmap或者数组[]表示，键为元素，值为出现次数。
• 需求集合need同样用一个hashmap或者数组[]表示，键为元素，值为出现次数
  • 只有当元素在need中存在时，才考虑移进或者移出窗口

代码实现

解法一：使用HashMap实现，会慢一些、但是标标准准整整齐齐。要注意：

• 两个Integer值比较时，要用a.equals(b)，因此超过[-128,127]就会new一个对象来比较
• 变量min 和 start end用于保存某一次结果，放在循环外面（全局作用域）

class Solution {
    public String minWindow(String s, String t) {
        //搞两个hashmap存字符串，键是字符，值是出现的次数
        Map<Character,Integer> window = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        //初始化need集合
        for(int i=0;i<t.length();++i){
            char a = t.charAt(i);
            need.put(a,need.getOrDefault(a,0)+1);
        }
        //还要先算一下need的size,用于之后判断是否完全匹配了
        int needLength = need.size();
        int left = 0, right=0;
        int match = 0; //匹配次数，一个字符算一个 与needLength相等时代表匹配完全
        //如果满足条件 要找最小子串还要保存子串的位置
        int min=Integer.MAX_VALUE; int start=0,end=0;
        while(right<s.length()){
            //待移字符
            char c = s.charAt(right);
            //右移窗口
            right++;
            //窗口数据更新，如果need中有c 就将c加入到win窗口中
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                //如果win中该字符个数与need中相同 则这个字符匹配成功
                if(window.get(c).equals(need.get(c))) match++;
            }

            //这里输出一个当前窗口的范围 方便调试
            //System.out.println("["+left+","+right+")");

            //判断左侧窗口是否需要收缩、收缩条件是都匹配上了
            while(match==needLength){
                //这里要小于min才赋start和end的值
                if(right-left<min){
                    start = left; end = right;
                    min = right-left;
                }
                char d = s.charAt(left);
                //左移窗口
                left++;
                //数据元素更新,如果d不在need中无需操作，如果在则win中相应得值-1
                if(need.containsKey(d)){
                    //如果刚好该元素移出前除以匹配状态 需要match--
                    if(window.get(d).equals(need.get(d))) match--;
                    window.put(d,window.getOrDefault(d,1)-1);
                }
            }
        }
        if(min == Integer.MAX_VALUE) return "";
        return s.substring(start,end);
    }
}

解法二：字符串的ASCII表总长128，可以用“桶”的思想，将目标子串放在含128个坑的桶中，效率挺高

使用数组存值，可以直接使用char字符作为数组的索引

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        int[] win = new int[128];
        //将字符串t中的字符存入need桶中
        for(int i=0;i<t.length();i++){
            need[t.charAt(i)]++;
        }
        int lengthOfNeed =0;
        for(int i:need){
            if(i!=0) lengthOfNeed++;
        }
        //窗口
        int left=0,right=0;
        //匹配次数match
        int match=0,start=0,end=0,min=Integer.MAX_VALUE;
        while(right<s.length()){
            //右移窗口
            char c = s.charAt(right);
            right++;
            //如果c存在与need中，就将它加入到win里面
            if(need[c]!=0){
                win[c]++;
                //如果在c索引处win的值和need的值相等了认为这个位置匹配了 即match+1
                if(need[c]==win[c]) match++;
            }
            
            //当所有的字符都匹配上了之后才开始紧缩窗口、如果没有就一直right往后移
           while(match==lengthOfNeed){
                //获取结果
                if(right-left<min){
                    start=left;end=right;min=right-left;
                }
                //left后移紧缩窗口
                char ch=s.charAt(left);
                left++;
                //如果left指向的元素不在need字符集则直接下一步，如果在就看看match是否需要减一
                if(need[ch]!=0){  //如果在need中
                    //只有当win[ch]=need[ch]时 后移才需要match--；
                    if(win[ch]==need[ch]) match--;
                    win[ch]--; //如果不等于，直接减少一个当前c索引处值即可
                }
            }
        }
        //如果min值没有变就代表 没有满足条件得子字符串
        if(min==Integer.MAX_VALUE) return "";
        //否则返回start到end得子字符串
        return s.substring(start,end);
    }
}

2.2 力扣567.字符串的排列

https://leetcode-cn.com/problems/permutation-in-string/

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

示例 1：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

思路分析

借鉴上一题最小覆盖子串的思维，当win的长度与need的长度相同，且其中的元素的数量能够一一对应时说明win中此时是need的一个全排列之一。

win依然用一个map集合或者桶数组表示，并且win里面只存need中有的元素，用来校对是否完全匹配。实际窗口的大小还是right-left；need依然用一个map集合或者桶数组表示，need只存需求中不重复的元素，并且计数用来校对匹配。实际需求的长度是待匹配的字符串的长度s.length()

还是分析收缩条件、窗口右移更新和窗口左移更新：

• 收缩条件：这里貌似是一个定长窗口，当窗口长度right-left超过子串的长度时就应该收缩了

  • 也可以参考上一题的，当完全匹配时收缩，可能效率会低一些

• 窗口右移更新：

  • 右指针右移后，如果该元素位于need集合中，就将之添加进win；
  • 如果该字符的个数也匹配了，则match++

• 窗口左移更新：

  • 左指针右移后，如果该元素位于need中，将之移出win
  • 如果该字符移出以之前是完全匹配的，则需要match–

代码实现

因为只含有小写字母，所以桶的大小定为26，用字符char求索引时减去’a’即可

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //建两个桶
        int[] need = new int[26];
        int[] win = new int[26];
        //将目标子串粘贴进need桶中、并计算桶非0的数量
        for(int i=0;i<s1.length();++i) need[s1.charAt(i)- 'a']++;
        int lengthOfNeed=0;
        for(int i:need){if(i!=0) lengthOfNeed++;}

        int left=0,right=0,match=0;
        while(right<s2.length()){
            //right右移一格
            char c = s2.charAt(right);
            right++;
            //如果当前字符在need中就将其加入到win中
            if(need[c- 'a']!=0){
                win[c- 'a']++;
                //如果win中c处的值（即个数）与need相等，则match+1
                if(win[c- 'a']==need[c- 'a']) match++;
            }
            
            //打印区间用于调试
            //System.out.println("["+left+","+right+")");
            
            //当前窗口长度大于等于子串的长度时，需要紧缩窗口
            while(right-left>=s1.length()){
                //如果数量和长度都匹配上了就return true
                if(match==lengthOfNeed) return true;
                char d = s2.charAt(left);
                left++;
                //如果d对应的元素为0个这left直接后移，无需其他操作
                //如果不为0个，则判断是否需要match--
                if(need[d- 'a']!=0){
                    //没有匹配上就计算match的值，看是否需要-1
                    if(win[d- 'a']==need[d- 'a']) match--;
                    win[d- 'a']--;
                }
            }
            
        }
        return false;

    }
}

2.3 力扣438.找到字符串中所有字母异位词

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：字母异位词指字母相同，但排列不同的字符串不考虑答案输出的顺序。

示例 2:
输入: s: “abab” p: “ab”
输出: [0, 1, 2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。

思路分析

只要出现全排列之一就把起始索引存入结果集合中，其他的和567字符串的排列相似。还是简单分析一下收缩条件、窗口右移更新和窗口左移更新：

• 收缩条件：为定长窗口，窗口长度>字符p的长度，就表示要收缩了
• 窗口右移更新：当need中含当前元素，就将之加入win集合中；如果该字符完全匹配了（个数相同）则match++;
• 窗口左移更新：先判断是否完全匹配，是就加入结果集。然后如果该元素位于need中，就更新match和win

代码实现

做了上一题，这题也就没什么意思了

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //和之前的差别就是保存起始索引而已 还是定长的窗口
        int[] win = new int[26];
        int[] need = new int[26];
        //初始化need
        for(int i=0;i<p.length();++i){
            need[p.charAt(i)-'a']++;
        }
        int lengthOfNeed = 0;
        for(int i:need){
            if(i!=0) lengthOfNeed++;
        }
        int match =0;
        List<Integer> res = new ArrayList<Integer>();
        int left=0, right=0;
        while(right<s.length()){
            int c = s.charAt(right)-'a';
            right++;
            //如果need中有，则加入win中
            if(need[c]!=0){
                win[c]++;
                if(win[c]==need[c]) match++;
            }

            //打印区间 便于调试
            //System.out.println("["+left+","+right+"]");

            while(right-left>=p.length()){
                //如果匹配上了 加入结果集中,这里窗口最多等于p的长度
                if(match==lengthOfNeed)  res.add(left);
                int d = s.charAt(left)-'a';
                left++;
                if(need[d]!=0){
                    if(win[d]==need[d]) match--;
                    win[d]--;
                }
            }
        }
        return res;
    }
}

2.4 力扣3.无重复字符的最长子串

思路分析

如果出现重复元素就紧缩窗口、紧缩窗口时需要移出left对应的元素。使用一个hashSet集合或者桶数组作为窗口win；需求集合就是窗口本身、要求是不出现重复元素。还是分析收缩条件、窗口右移更新、窗口左移更新：

• 收缩条件：当win中出现了重复元素就需要跟紧缩窗口、知道没有重复元素
  • 其实每次加入的是right，所以重复的也只可能是right对应的元素
• 窗口右移更新：right++后，将right加入win集合，其实加不加都无所谓，反正清除重复之后、还要将它重复加入的
• 窗口左移更新：去掉位于left上重复的元素，如果清除完了、记得添加一个回来

代码实现

求得是最长的字符串长度，所以要记录好每次的窗口大小并与之前的取大值

方法一：用hashset作为窗口集合 8ms

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left=0, right=0;
        int max=0;
        Set<Character> win = new HashSet<>();
        while(right<s.length()){
            char c = s.charAt(right);
            right++;
            //先不加入，待清除重复的之后再加入

            //System.out.println("["+left+","+right+"]");

            while(win.contains(c)){
                char d = s.charAt(left);
                left++;
                win.remove(d);
            }
            win.add(c);
            max = Math.max(max,right-left);
        }
        return max;
    }
}

方法二：用桶数组作为win集合 3ms

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //用数组保存元素，桶的思想做做看
        if(s.length()==0) return 0;
        int[] win = new int[128];
        int left=0,right=0,max=1;
        while(right<s.length()){
            char c = s.charAt(right);
            right++;
            //将c加入桶中
            win[c]++;
            //当出现重复元素时，缩紧窗口
            while(win[c]>1){
                char d = s.charAt(left);
                left++;
                win[d]--;
            }
            max=Math.max(max,right-left);
        }
        return max;
    }
}

2.5 剑指offer.59-1 滑动窗口的最大值（hard)

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
滑动窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

思路分析

这题真狗、我又没做出来….

思路其实也挺简单、代码实现一下有点绕。就是一个固定长度为k的窗口，窗口使用双端队列的结构、始终保持窗口队列中元素的降序属性（因为较小的值无用可以舍弃）。没滑动一次窗口、就取出队首元素存入结果的数组中。需要注意：

• 因为涉及出队和入队的问题，right由0开始，而left由0-k+1处开始，每滑动一次窗口、right和left都需要+1
• 紧缩窗口：就是当队首元素是上一个窗口left位置的值时（也即是现在的left-1），需要先从队列中移除
  • 刚开始left为负，所以要注意left的范围
• 保持队列的降序并添加元素：如果队尾的元素小于要新加的元素 则删除，，直到删干净再加入新元素

代码实现

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0||nums==null) return new int[0];
        //还是滑动窗口的思想，只是用双端队列作为窗口，维持一个递减的序列，最大值总是在队首
        Deque<Integer> deque = new LinkedList<>();
        int right =0; int left = 1-k;
        int[] res = new int[nums.length-k+1];

        while(right<nums.length){
            int c = nums[right];
            right++;
            //添加新元素，并要保持降序
            while(deque.peekLast()!=null && deque.peekLast()<c){
                deque.removeLast();
            }
            deque.offerLast(c);

            //区间范围
            //System.out.println("["+left+","+right+")");

            //如果left>=1: 队首和要移除的nums[left-1]相等 , 删除队首元素 
            if(left>=1 && deque.peekFirst()==nums[left-1]){
                deque.removeFirst();
            }
            //添加进结果集
            if(left>=0) res[left]=deque.peekFirst();
            left++;
        }
        return res;
    }
}

3 总结一下

每次刷几道同一类型的经典题，总结一下还是很有好处的。

滑动窗口不外乎两个集合窗口集合windows和需求集合need和两个指针left\right，需求集合首先根据要求将需求集合初始化，然后while循环中right指针不断向前推进、left指针在窗口需要收缩是向右移动，并窗口扩大和收缩过程都需要更新窗口内的数据。while内部伪代码步骤如下：

while(right<length){
    //1取出当前窗口最右侧元素
    int c = nums[right];
    //窗口右指针右移
    right++;
    //2窗口内的数据更新
        
    //打印窗口范围方便调试
	System.out.println("["+left+","+right+")");
    
    while(需要紧缩窗口){
        //3保存当前窗口的信息
        res = right-left;
        //4取出左侧元素
        int d = nums[left];
        //窗口左指针右移
        left++;
        //5窗口内元素更新 
    }  
}

值得注意的是：

• 结果集的获取和保存一般放在紧缩窗口的while循环内，窗口紧缩的条件也包括窗口（大小）正满足条件的情况
• 作为窗口集合和需求集合，可以选用hashmap或者hashset这样的集合、有时也可以使用数组以桶的形式储存元素

其实有些时候模板也解决不了问题，比如2.5那道滑动窗口最大值，只能说循环迭代的流程需要自己整明白了、在按模板的套路来解题，你的代码能更规范、更共通一些。共勉。