76. 最小覆盖子串（滑动指针）

喜欢ヅ旅行 2023-10-05 20:12 2阅读 0赞

#### 76. 最小覆盖子串 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

主要搞清楚增大窗口，直至包含T中所有字符后停下来，然后不断收缩窗口，直到窗口中的字符串不再满足要求。**然后重复上面的两个步骤即可。**

**其实还是只要套模板，具体思路见书87面**

## 代码 ##

class Solution {
        
        public String minWindow(String s, String t) {
        
            //存放我们需要的字串的字符，以及他们的个数，比如t为“ABC”，那么need{A:1,B:1,C:1}
            Map<Character, Integer> need = new HashMap<>();
            //滑动窗口
            Map<Character, Integer> window = new HashMap<>();
    
            for (char c : t.toCharArray()) {
        
                //取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
    
            int left = 0;
            int right = 0;
            int valid = 0;//窗口中已经满足need中条件的字符个数。比如窗口已经有一个A了，那么valid=1
    
            // 记录最小覆盖字串的起始索引及长度
            int start = 0, len = Integer.MAX_VALUE;
    
            while (right < s.length()) {
        
                //c：即将移入窗口的字符
                char c = s.charAt(right);
                //右移窗口
                right++;
                //进行窗口内一系列数据的更新
                if (need.containsKey(c)) {
        
                    //把C移入窗口，同时记录该字符出现的次数
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    //如果该字符已经达到了need的要求，就可以把valid+1了。
                    /*
                        最后一个测试用例一直过不了，因为定义的Map的value类型为Integer是对象，
                        Integer会缓存频繁使用的数值[-128,127]，超过此范围就会new一个对象，
                        导致使用“==”错误，改为equals()即可。
                    */
                    if (window.get(c).equals(need.get(c))) {
        
                        valid++;
                    }
                }
    
                //判断左侧窗口是否需要收缩
                //本题中收缩的条件是窗口中的字符已经符合了要求
                while (valid == need.size()) {
        //需要的字符个数已经全部满足了
                    if (right - left < len) {
        //right - left：当前窗口的长度
                        start = left;
                        len = right - left;
                    }
    
                    //d是即将移出窗口的字符
                    char d = s.charAt(left);
                    //收缩窗口左边界
                    left++;
                    if (need.containsKey(d)) {
        
                        if (window.get(d).equals(need.get(d))) {
        
                            valid--;//合适的字符减少了一种
                        }
                        //在window中也要将该字符出现的次数减少1
                        window.put(d, window.getOrDefault(d, 0) - 1);
                    }
                }
            }
    
    
            //如果len没动过，证明不能满足题目的条件，如果动过，证明可以满足，截取出来该字串即可
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210222211234950.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70