力扣 之 最小覆盖子串（变长滑动窗口，越短越好）

文章目录

76.最小覆盖子串

• 思路分析：
  • 一般思路：一开始看到这个题目，可能大家的第一个印象就是，就是需要不断枚举出s中所有的子串，然后再统计里面的各种字符的数量和种类，然后再与这个字符t作比较，但是这样的话，这个思路就十分宽泛，根本就是无从下手
  • 需要思考什么？：
    • 枚举顺序：这个枚举的话，还是讲求一个顺序性，我们通过固定左端点，枚举右端点的思路，可以比价有效的进行一个枚举
    • 判断是否满足？： 对于是否满足，那么就是对于子串和字符串t来说，至少t中对应种类和数量的字符要满足
    • 更新方式：对于满足之后的更新主要是通过移动这个窗口的左端点来解决

思路1：通过两个向量，由于题目说了，存在大小写两种情况，那么就是我们可以开两个128长度的向量，分别统计两个字符串中字符的数量，那么这样的时候复杂度也就是O(128m+n)

class Solution {bool issame(vector<int> stores,vector<int> storet){for (int i = 'A';i <= 'Z';i++){if (stores[i] < storet[i]){return false;}}for (int i = 'a'; i <= 'z';i++){if (stores[i] < storet[i]){return false;}}return true;
}public:string minWindow(string s, string t) {vector<int> stores(128),storet(128);// 先存储字符串t的情况for (char c:t){storet[c]++;}int ansleft = -1,ansright = s.length(),left = 0;for (int right = 0; right < s.length();right++){stores[s[right]]++;while (issame(stores,storet)){if (right - left < ansright - ansleft){ansleft = left;ansright = right;}stores[s[left]]--;left++;}}return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);}
};

思路2：（思路1的优化）

• 使用变量less统计字符串t中不同种类的字符串的数量，并且定义这个向量store[i] = storet[i] - stores[i]

class Solution {
public:string minWindow(string s, string t) {vector<int> store(128);int less = 0;for (char c:t){if (store[c] == 0){less ++;}store[c] ++;}int m = s.size();int ansleft = -1,ansright = m,left = 0;// 定义的这个 cnt[i] 为字符 i 还需满足的数量for (int right = 0;right < m; right ++){store[s[right]] -- ;if (store[s[right]] == 0){// 刚好满足less --;}while (less == 0){//全部都满足if (right - left < ansright - ansleft){ansleft = left;ansright = right;}// 需要检查移动左端点对less的影响if (store[s[left]] == 0){less ++;}store[s[left]] ++;left++;}}return ansleft < 0 ? "" : s.substr(ansleft ,ansright - ansleft + 1);}
};