LeetCode练习题--567.字符串的排列

今天讲一个非常经典的滑动窗口的问题

这道题的意思很明显:

给你两个字符串s1与s2,判断s2中是否存在一个子串:它包含s1中所有字符且不包含其他字符

让我们先来写一下滑动窗口的模板:

    /**
     * 滑动窗口模板 
     * @param s1 
     * @param s2 
     */
    public static void model (String s1, String s2) {
        //用HashMap充当窗口
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for(char c : s1.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        }//将s1放入需要的目标的值
        int left = 0, right = 0;//左右窗口
        int valid = 0;//满足目标的值
        while (right < s2.length()) {//left<right可写可不写,恒为true
            char c = s2.charAt(right);//拿到right
            right++;
            //判断右边进来的字母
            
                //相关代码
            
            //对左边界进行操作
            while (right - left >= s1.length()) {
                //相关代码
            }
        }
        return;
    }

接下来让我们一起做一下这道题

public static boolean checkInclusion (String s1, String s2) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (int i = 0; i < s1.length(); i++) {
        need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
    }
    int left = 0, right = 0;
    int valid = 0;
    while (right < s2.length()) {
        char c = s2.charAt(right);
        right++;//右移右边界
        //判断右边进来的字母
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);//将字符c放入window
            if (window.get(c).equals(need.get(c))) {
                valid++;//如果符合条件(window中该字符与need中相同)
            }
        }
        //对左边界进行操作
        while (right - left >= s1.length()) {
            if (valid == need.size()) {
//valid==need.size()的时候,right - left = s1.length()恒成立,无需多余判断
                return true;
            }
            char d = s2.charAt(left);
            left++;//右移左边界
            if (need.containsKey(d)) {
                //将字符d从window中删除
                if (need.get(d) == window.get(d)) {
                    valid--;//如果删除之前该元素在window中与need相同
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return false;
}

其中需要注意的点我都已经做了注解,如果还有什么地方不明白,可以私信我