算法学习：双指针进阶之滑动窗口算法_双指针 滑窗

 文章目录

• 一、认识滑动窗口算法
• 二、算法运用
  • 1.最小覆盖子串
  • 2.字符串排列
  • 3.找所有字母异位词
  • 4.最长无重复字串
• 总结

一、认识滑动窗口算法

        本文讲的滑动窗口算法基于前面的基本的双指针技巧。在滑动窗口算法中，可以使用左右指针来记录窗口的左右边界，以及使用快慢指针来同时从两端向中间遍历数据流，从而加速算法的执行效率。滑动窗口算法的核心在于通过维护一个窗口来记录满足条件的数据，并在窗口移动的过程中更新窗口记录的结果，其时间复杂度为O（n）。具体来说，滑动窗口算法通常包括以下几个步骤：

1. 初始化左右指针，表示窗口的左右边界。
2. 移动右指针，扩大窗口，直到找到符合条件的窗口。
3. 移动左指针，缩小窗口大小，直到不能再缩小为止。
4. 在窗口移动的过程中，记录窗口的状态，例如最大值、最小值、子串长度等等。
5. 返回窗口记录的结果。 

         下面是滑动窗口算法的核心框架：

/* 滑动窗口算法框架 */
void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的数据
    HashMap<Character, Integer> window = new HashMap<>();
 
    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...
 
        /*** debug 输出的位置 ***/
        System.out.printf("window: [%d, %d)\n", left, right);
        /********************/
 
        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            window.put(d, window.get(d) - 1);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

二、算法运用

1.最小覆盖子串

        下面选用力扣的第 76 题「最小覆盖子串」练习,详情请读者自动跳转至原题。

        该题的思路是建立need（记录目标个数）和window（记录当前窗口内满足条件的目标个数）两个计数器，通过扩大右窗口来找到可行解，而后通过缩小左窗口来找到最优解,直到右窗口到达数组的最右边。

代码如下（示例）：

class Solution {
    public String minWindow(String s, String t) {
                 // 用于记录需要的字符和窗口中的字符及其出现的次数
                Map<Character,Integer> need = new HashMap<>();
                Map<Character,Integer> window = new HashMap<>();
                //计算字符串t中每个字符的出现次数，并将结果存储在need
                for(char c : t.toCharArray()) 
                    need.put(c,need.getOrDefault(c,0)+1);//根据当前计数情况+1，首次出现则返回0并且+1
 
                int left=0,right=0;
                int valid =0;//窗口中满足的字符个数
                //记录最小覆盖子串的起始索引及长度
                int start=0,len=Integer.MAX_VALUE;
 
                //寻找可行解
                while(right<s.length()){
                    //获取移入窗口的字符
                    char c= s.charAt(right);
                    //移右窗口
                    right++;
                    //窗口更新
                    if(need.containsKey(c)){
                        window.put(c,window.getOrDefault(c,0)+1);
                        //valid记录目前满足的字符个数，直到找到可行解，前往下一步找到最优解
                        if(window.get(c).equals(need.get(c)))
                            valid++;
                    }
                    //找到可行解后通过移动左窗口找到最优解
                    while(valid==need.size()){
                        //更新最小覆盖子串
                        if(right-left<len){
                            start=left;
                            len=right-left;
                        }
                        //获取移除窗口的字符
                        char d = s.charAt(left);
                        //移左窗口
                        left++;
                        //窗口更新
                        if(need.containsKey(d)){
                            //valid记录目前满足的字符个数，直到不再满足可行解，前往上一步再次移右窗口找到可行解
                            if(window.get(d).equals(need.get(d)))
                            valid--;
                            window.put(d, window.get(d) - 1);
                         }    
                    }
                }
            //返回最小覆盖子串
            return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}

2.字符串的排列

       下面选用力扣的第 567 题「字符串的排列」练习,详情请读者自动跳转至原题。

        本题的解题思路也是运用到了滑动窗口算法，需要修改的地方在于题目要求的不同。本题要求S1的排列之一是S2的子串。也就是说S1存在S2，且这个子串不包含另外的其他字符，不同于第一题。本题需要注意以下几点：

1.判断是否要缩小左窗口在于整个窗口长度是否大于S2本身

2.本题并不是要求寻找最优解，而是优先找到S2，所以当valid == need.size()，即满足条件要求，此时立即返回true，不必再次遍历完整个数组。

3.本意的可行解也不同于上面一题，这里的可行解以s1本身的长度为单位，也就是说当找到与s1相似的子串时，就开始判断窗口内的子串是否是s1

代码如下（示例）：

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // 用于记录需要的字符和窗口中的字符及其出现的次数
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        //计算字符串t中每个字符的出现次数，并将结果存储在need
        for(int i =0; i<s1.length();i++){
            char c = s1.charAt(i);
            need.put(c,need.getOrDefault(c,0)+1);//根据当前计数情况+1，首次出现则返回0并且+1        
            }
 
            int left=0,right=0;
            int valid=0;//窗口中满足的字符个数
 
             //寻找可行解
            while(right<s2.length()){
                //获取移入窗口的字符
                char c=s2.charAt(right);
                //移右窗口
                right++;
                //窗口更新
                if(need.containsKey(c)){
                    //valid记录目前满足的字符个数，直到找到可行解
                    window.put(c,window.getOrDefault(c,0)+1);
                    if(window.get(c).equals(need.get(c)))
                    valid++;
                }
 
                //找到可行解后通过移动左窗口找到S1
                while(right-left>=s1.length()){
                    //成功找到S1
                    if(valid==need.size())
                        return true;
                    //获取移除窗口的字符
                    char d=s2.charAt(left);
                    //缩小窗口
                    left++;
                    //窗口更新
                    if(need.containsKey(d)){
                        //valid记录目前满足的字符个数，直到不再满足可行解，前往上一步再次移右窗口找到可行解
                        if(window.get(d).equals(need.get(d)))
                            valid--;//
                        //减少d字符在窗口记录中的次数
                        window.put(d,window.get(d) - 1);
                    }
 
                }
            }
            //未找到S1
            return false;
    }
}

3.找所有字母异位词

       下面选用力扣的第 438 题「找到字符串中所有字母异位词」练习,详情请读者自动跳转至原题。

        该题的基本思路和上一题相同，本质就是排列。不同点在于本题要求返回所有满足条件的结果集，这里用到了List<Integer> res = new ArrayList<>();来存结果集。

代码如下（示例）：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 用于记录需要的字符和窗口中的字符及其出现的次数
            Map<Character,Integer> need = new HashMap<>();
            Map<Character,Integer> window = new HashMap<>();
        //计算字符串p中每个字符的出现次数，并将结果存储在need
            for(char c: p.toCharArray())
            need.put(c,need.getOrDefault(c,0)+1);//根据当前计数情况+1，首次出现则返回0并且+1 
 
            int left=0,right=0;
            int valid=0;//窗口中满足的字符个数
            List<Integer> res = new ArrayList<>();//把符合条件的起始索引存到集合中
            //寻找可行解
            while(right<s.length()){
                char c =s.charAt(right);
                right++;
                //窗口更新
                if(need.containsKey(c)){
                    //valid记录目前满足的字符个数，直到找到可行解
                    window.put(c,window.getOrDefault(c,0)+1);
                    if(window.get(c).equals(need.get(c)))
                    valid++;
                }
                //找到可行解后通过移动左窗口找到p的异位词
                    while(right-left>=p.length()){
                            if(valid==need.size())
                                res.add(left);//将索引插入集合中
                            char d =s.charAt(left);
                            left++;
                            //窗口更新
                            if(need.containsKey(d)){
                                //valid记录目前满足的字符个数，直到不再满足可行解，前往上一步再次移右窗口找到可行解
                                if(window.get(d).equals(need.get(d)))
                                valid--;
                                window.put(d,window.get(d)-1);
 
                            }
                    }
            }
            //返回所有结果集
             return res;
        }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //用来记录窗口内各个字符的个数
        Map<Character,Integer> window = new HashMap<>();
 
        int left=0,right=0;
        int len=0;//记录最长子串长度
        //找到可行解
        while(right<s.length()){
            char c= s.charAt(right);
            right++;
            //更新窗口
            window.put(c,window.getOrDefault(c,0)+1);
            //此时找到重复项，并将其移除
            while(window.get(c)>1){
                char d = s.charAt(left);
                left++;
                window.put(d,window.getOrDefault(d,0)-1);
            }
            //记录最大长度
            len = Math.max(len, right - left);
        }
        return len;
    }
}

总结

        滑动窗口算法基于左右指针和快慢指针的基础上，其主要应用于字符串排列的判断，相较于仅仅使用双指针，效率会更高。其特点在于创造了计数器，再加上窗口移动（指针移动）。在字符串排列判断这一类型上优先选择滑动窗口算法。