题解 | #牛群名字覆盖#

考察知识点：滑动窗口

题目分析：

可以通过使用动态的滑动窗口解决问题。首先left和right指向最开始，然后只让right向右移动，每遍历到一个需要的字符时就记录下来。当left和right之间的字符满足条件时，right指针不动，left向右移动，每次遍历到一个需要的字符时需要将相应的字符减一，看是否仍满足条件。直到不满足条件的前一个字符，就是这一次找到的最短的满足需求的字符串。

到这时还没有结束，因为还没有遍历完整个数组，右边可能还有更短的。所以让right继续向右走，直到遍历完整个数组为止。

所用编程语言：C++

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return string字符串
     */
    bool meetConditions(unordered_map<char, int> &need, unordered_map<char, int> &window) {
        for (auto item: need) {
            if (item.second > window[item.first]) 
                return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        // write code here
        int left = 0, right = 0;
        int minLength = 0x3f3f3f3f;
        int start = 0;
        int size = s.size();
        unordered_map<char, int> need;
        unordered_map<char, int> window;
	  //记录需求
        for (auto &ch : t) 
            need[ch]++;
	//使用滑动窗口进行查找
        while (right < size) {
            char ch = s[right++];
            if (need[ch]) window[ch]++;
            while (meetConditions(need, window)) {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    start = left;
                }
                char ch = s[left++];
                if (need[ch]) window[ch]--;
            }
        }
        if (minLength != 0x3f3f3f3f) return s.substr(start, minLength);
        else return "";
    }
};

动态滑动窗口的代码模板：

该模板来自惊鸿只为卿

int left = 0,right =0;
while(right指针未越界){
  char ch = arr[right++];
  //右指针移动，更新窗口
  ...
  
  //窗口数据满足条件 对于固定窗口而言，就是窗口的大小>=固定值；对于动态窗口，就是从left出发，窗口不断扩充，第一次满足题意的位置
  while(窗口数据满足条件){
  	//记录或者更新全局数据
  	...
  	
  	//右指针不动，左指针开始移动一位
  	char tmp = arr[left++];
  	
  	//左指针移动，窗口缩小，更新窗口数据
  	...
  }
  //返回结果
  ...
}