[数据结构与算法]【la】滑动窗?算法

滑动窗口问题应该考虑的四个问题
1、当移动 right 扩?窗?，即加?字符时，应该更新哪些数据？
2、什么条件下，窗?应该暂停扩?，开始移动 left 缩?窗?？
3、当移动 left 缩?窗?，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩?窗?时还是缩?窗?时进?更新？

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。
返回 s 中涵盖 t 所有字符的最小子串。
如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

 

注意：

    对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    如果 s 中存在这样的子串，我们保证它是唯一的答案。

 

示例 1：

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

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：
    1 <= s.length, t.length <= 105
    s 和 t 由英文字母组成


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
   public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        for (int i = 0;i < t.length();i++){
            char key = t.charAt(i);
            need.put(key, need.getOrDefault(key,0)+1);
        }

        int left = 0,right = 0;
        // left 和 right 变量初始化窗?的两端,区间 [left, right) 是左闭右开的
        int valid = 0;
        // valid 变量表示窗?中满? need 条件的字符个数
        // 如果 valid 和 need.size 的??相同，则说明窗?已满?条件，已经完全覆盖了串 T。
        // 比如说 t = abc, window = abba, 那么此时 valid = 2

        int max = s.length()+1;
        int start = 0,len = max;
        // 记录 最小覆盖子串的起始索引长度
        while (right < s.length()){
            // 开始滑动
            char key = s.charAt(right);
            // c 是 将移入窗口的字符
            right ++;
            // 窗口右移
            if (need.containsKey(key)){
                // 如果 need 里有 key ，再把key放入 window，不要给 窗口中放没用的字符
                window.put(key,window.getOrDefault(key,0)+1);
                // 更新 window 中 key = s.charAt(right-1) 对应的 value 值
                if(window.get(key).equals(need.get(key))){
                    valid++;
                }
            }
            while (valid == need.size()){ // 判断窗口左侧是否要收缩
               // [left,right) 之间 len = right - left
                if(right-left < len) {
                    // 更新最小子串
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                // d 是要移除窗口的值
                left++;
                if (need.containsKey(d)){
                    // 进行窗口内数据一系列更新
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }

        if (len == max){
            return "";
        }
        return s.substring(start,start+len);
    }
}

注意 ： Java 的 Integer，String 等类型判定相等应该? equals ?法?不能直接?等号 ==

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

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

示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：
left 右移的条件：当区窗口中完整包含 目标串s1，left右移，区间缩小。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // s1 的排列之一是 s2 的 子串
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        // 把 s1 的字符放入 need 中
        for (int i = 0;i < s1.length();i++){
            char key = s1.charAt(i);
            need.put(key,need.getOrDefault(key,0)+1);
        }
        int valid = 0;
        int left = 0, right = 0;
        // 窗口区间：[left,right)

        while (right < s2.length()){

            char key = s2.charAt(right);
            right++;

            // 窗口右移
            if (need.containsKey(key)){
                // s1 中 包含 字符 key
                window.put(key,window.getOrDefault(key,0)+1);
                if (window.get(key).equals(need.get(key))){
                    valid++;
                }
            }

            /**
             * 例如：
             * 输入：s1= "ab" s2 = "eidboaoo"
             * 输出：false
             * right 右移至 窗口 包括 "eidboa“ ，right 停止右移
             * left 开始右移，到窗口包括 "boa“ 停止，right-left = 3 > s1.length()
             * 把 left 此时指向的 'b'（在窗口中），移除窗口
             * left 停止右移，right 开始右移
             */
            // 窗口缩小
            while (valid == need.size()){
                char del = s2.charAt(left);
                if (window.containsKey(del)){
                    if (right-left == s1.length()){
                        return true;
                    }
                    else {
                        // 否则，就要把这个 key 移出窗口
                        if (window.get(del).equals(need.get(del))){
                            valid--;
                        }
                        window.put(del,window.get(del)-1);
                    }
                }
                left++;
            }

        }
        return false;
    }
}

方法二：
left 间右移条件：当窗口中包含的 元素个数 大于等于 目标串 s1 的元素个数时

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // s1 的排列之一是 s2 的 子串
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        // 1. 把 s1 的字符放入 need 中
        for (int i = 0;i < s1.length();i++){
            char key = s1.charAt(i);
            need.put(key,need.getOrDefault(key,0)+1);
        }
        int valid = 0;
        int left = 0, right = 0;
        // 窗口区间：[left,right)

        while (right < s2.length()){

            char key = s2.charAt(right);
            right++;

            // 窗口右移
            if (need.containsKey(key)){
                // s1 中 包含 字符 key
                window.put(key,window.getOrDefault(key,0)+1);
                if (window.get(key).equals(need.get(key))){
                    valid++;
                }
            }

            while (right - left >= s1.length()){

                if (valid == need.size()){
                    return true;
                }
                char del = s2.charAt(left);
                if (window.containsKey(del)){
                    if (window.get(del).equals(need.get(del))){
                        valid--;
                    }
                    window.put(del,window.get(del)-1);
                }
                left++;
            }

        }
        return false;
    }
}

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，
返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。


示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {

        ArrayList<Integer> list = new ArrayList<>();
        // 找到 s 中所有 p 的 异位词 的子串
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        // 1. 把 s1 的字符放入 need 中
        for (int i = 0;i < p.length();i++){
            char key = p.charAt(i);
            need.put(key,need.getOrDefault(key,0)+1);
        }
        int valid = 0;
        int left = 0, right = 0;
        // 窗口区间：[left,right)

        while (right < s.length()){

            char key = s.charAt(right);
            right++;

            // 窗口右移
            if (need.containsKey(key)){
                // s1 中 包含 字符 key
                window.put(key,window.getOrDefault(key,0)+1);
                if (window.get(key).equals(need.get(key))){
                    valid++;
                }
            }

            while (right - left >= p.length()){

                if (valid == need.size()){
                    list.add(left);
                }
                char del = s.charAt(left);
                if (window.containsKey(del)){
                    if (window.get(del).equals(need.get(del))){
                        valid--;
                    }
                    window.put(del,window.get(del)-1);
                }
                left++;
            }

        }
        return list;
    }
}

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

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0,right = 0;
        int len = 0; // 最大 子串的长度
        while (right < s.length()){
            char key = s.charAt(right);
            right++;
            map.put(key,map.getOrDefault(key,0)+1);
            // left 右移：窗口中 字符 key 的个数超过1
            while (map.get(key) > 1){
                char del = s.charAt(left);
                left++;
                map.put(del,map.get(del)-1);
            }
            // 更新 len
            if (right - left > len){
                len = right - left;
            }
        }
        return len;
    }
}