滑动窗口解题总结

---

一、算法简介

滑动窗口是一种高级双指针技巧的算法框架，代码模板可以按照如下表示

int left = 0,right = 0;      //1.初始化双指针，建立一个索引闭区间，也就是窗口
						   //2.定义求解目标的初始值
while(right < s.length()){   
    window.add(s[right]);    //3.通过增加right指针不断地扩大窗口  （找到可行解）
                             //并同时更新求解的目标值
    right++;
    while(valid){               //4.判断当前窗口是否满足要求
        window.remove(s[left]); //5.停止增加right指针，转而增加left指针，直至窗口中的数据不符合要求
                                //  并同时更新求解的目标值
        left++;                 //6.继续循环
    }
}

其中的window的数据类型一般为哈希表，当然在存储英文字母时也可以使用数组；代码的关键点如何判断

滑动窗口是有效的

二、典型例题

1.Leetcode 3

给定一个字符串，找出其中不含有重复字符的最长子串的长度

class Solution {
    private Map<Character,Integer> window = new HashMap<>();  //定义存储元素出现次数的哈希表
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0) return 0;
        int left = 0,right = 0;                               //初始化左右指针
        int maxLen = 0;                                       //初始化最大长度
        while(right < s.length()){
            if(!window.containsKey(s.charAt(right))){         //判断当前元素是否已经存在
                window.put(s.charAt(right),1);                //不存在就存入哈希表
                maxLen = Math.max(maxLen,right - left + 1);   //更新最大长度
                right++;                                      //向右扩大窗口
            }else{
                while(window.containsKey(s.charAt(right))){   //如果已经包含那就从左边删除元素直至不包含
                    window.remove(s.charAt(left));
                    left++;                                   //从左边缩小窗口
                }
            }
        }
        return maxLen;
    }
}

题目的框架都是相似的，不同的是如何判断当前窗口的有效性

2.Leetcode 438

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，子串起始索引

class Solution {
    private List<Integer> res = new ArrayList<>();                //存储结果的列表
    private Map<Character,Integer> need = new HashMap<>();        //子串哈希表
    private Map<Character,Integer> window = new HashMap<>();      //滑动窗口哈希表
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length() == 0) return res;
        int left = 0,right = 0;                                   //初始化左右指针
        int match = 0;                                            //记录字符串匹配个数
        
        for(char c : p.toCharArray()){                            //构造子串哈希表
            need.put(c,need.getOrDefault(c,0) + 1);
        }
        
        while(right < s.length()){
            char c1 = s.charAt(right);
            if(need.containsKey(c1)){
                window.put(c1,window.getOrDefault(c1,0) + 1);
                if(window.get(c1).equals(need.get(c1))) match++;    //更新匹配的字符数目
                //整型对象的比较不能用“==”
            }
            right++;
            while(match == need.size()){                            //判断当前窗口是否满足要求    
                if(right - left == p.length()){                     //发现字母异位词
                    res.add(left);                                  //添加到返回结果中
                }
                char c2 = s.charAt(left);				
                if(need.containsKey(c2)){                           //从左边删除的元素在子串中出现
                    window.put(c2,window.get(c2)-1);                //在窗口哈希表中删除
                    if(window.get(c2) < need.get(c2)) match--;      //减少匹配的字符数 
                }
                left++;                                             //缩小滑动窗口
            }
        }
        return res;
    }
}

框架是一致的，不同的就是对窗口值有效性的判断