LCR 017

题目：LCR 017

解法：滑动窗口

1. 用Map存储t中各字母出现次数。

2. 建立双指针，左指针指向子串起始，右指针指向子串结尾。

3. 右指针扩张：若遍历元素在t中存在，Map对应value减1，当子串包含所有t中字符时，扩张结束，开始收缩。

4. 左指针收缩：若遍历元素在t中存在，Map对应value加1。当遇到第一个有效字符时，收缩结束。

    public String minWindow1(String s, String t) {
        int left = 0, len = 0;
        String res = "";
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }
        for (int right = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                if (map.get(s.charAt(right)) > 0) len++;//有效字符
                map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
            }
            if (len == t.length()) {
                while (!(map.containsKey(s.charAt(left)) && map.get(s.charAt(left)) == 0)) {
                    if (map.containsKey(s.charAt(left))) map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                    left++;
                }
                res = res.isEmpty() || res.length() > right - left + 1 ? s.substring(left, right + 1) : res;
                map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                left++;
                len--;
            }
        }
        return res;
    }

1. 问题：什么是有效字符？

   例如，当t=“abc”，s="abbbbc"时，s中实际有效字符只有’a’、‘b’、‘c’，中间多余的’b’均为无效字符，只有第一个’b’为有效字符。

2. 问题：如何判断子串已经包含了t中所有字符？

   • 方法一：数组各个元素都小于等于0。缺点：要遍历整个数组
   • 方法二：维护一个变量len，表示有效字符个数，右指针每遍历一个有效字符，len加1，当len为t.length时，子串已包含t中所有元素

3. 问题：右指针遍历时，如何判断该字符为有效字符？

   当数组对应位置元素大于0时(t中的该字符数>子串中该字符数)，该字符为有效字符。

4. 问题：左指针遍历时，如何判断该字符为有效字符？

   当数组对应位置元素等于0时(t中的该字符数=子串中该字符数)，该字符为有效字符。

5. 注意：

   • 维护len变量时，只有遍历到有效字符时，len才减1
   • 当左指针收缩遇到第一个有效字符时，保留此时子串长度，然后左指针继续右移，剔除该有效字符，向后寻找是否还有满足条件的子串