作文网网址_舆情监控系统_whois查询 站长工具_搜索引擎排名中国

---

题目链接：

76. 最小覆盖子串

---

题目描述：

---

解法

暴力解法：

列出所有符合要求的字串，然后比较大小。

滑动窗口+哈希表

比如，如果已经符合要求了

那么left右移一位的话，right需要移动吗？

1. left指向的地方恰好有符合t的字符，->right不动
2. left指向的地方恰好没有符合t的字符，->right动

解法：

1. left=0，right=0

2. 进窗口：hash2[in]++

3. 判断：check(hash1,hash2)

   更新结果：起始位置，最短长度

   决定是否出窗口：hash2(out)--

我们可以优化一下：

使用count来标记有效字符的种类。

之前标记的是有效字符的次数，这边是种类，因为如果是次数的话，t里面是ABC，1+1+1=3，s里面是BBC，那么2+1=3，是无法解决这个问题的。

1. 进窗口：进去之后，当hash2(in)==hash1(in);count++
2. 出窗口：出之前，当hash2(out)==hash1(out);count--
3. 判断条件：count==hash1.size()

---

C++ 算法代码：

class Solution 
{public:string minWindow(string s, string t) {int hash1[128] = { 0 }; // 初始化一个大小为 128 的整型数组 hash1，并将所有元素初始化为 0int kinds = 0; // 统计有效字符有多少种for(auto ch : t){ // 遍历字符串t，统计每个字符的频次，并计算不同字符的种类数if(hash1[ch]++ == 0) {kinds++;}}int hash2[128] = { 0 }; // 统计窗口内每个字符的频次int minlen = INT_MAX, begin = -1; // 记录最小窗口的长度，初始化为最大值，记录最小窗口的起始位置，初始化为-1for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];// 当前进入窗口的字符if(++hash2[in] == hash1[in]) // 更新hash2中该字符的频次{count++; // 进窗口 + 维护 count}while(count == kinds) // 当count等于kinds时，说明当前窗口包含t中所有字符{if(right - left + 1 < minlen) // 更新最小窗口的长度和起始位置{minlen = right - left + 1;begin = left;}char out = s[left++]; // 尝试缩小窗口，移除最左边的字符if(hash2[out]-- == hash1[out]) {count--; // 出窗口 + 维护 count}}}if(begin == -1) // 如果begin没有被更新，说明不存在包含t的窗口，返回空字符串{return "";}else{return s.substr(begin, minlen);// 否则，返回从begin开始的最小窗口子串}}
};

---

图解

例如：s = "ADOBECODEBANC", t = "ABC"

1. hash1[A]=1，hash1[B]=1，hash1[C]=1，kind=3

   left = 0, right = 0, count = 0，进入循环

   in=A，++hash2[in]=2，hash1[in]=2，count++，count=1

   right++

2. left = 0, right = 1, count = 1，进入循环

   in=D，++hash2[in]=2，hash1[in]=1，count=1

   right++

3. left = 0, right = 2, count = 1，进入循环

   in=O，++hash2[in]=2，hash1[in]=1，count=1

   right++

4. left = 0, right = 3, count = 1，进入循环

   in=B，++hash2[in]=2，hash1[in]=2，count++，count=2

   right++

5. left = 0, right = 4, count = 2，进入循环

   in=E，++hash2[in]=2，hash1[in]=1，count=2

   right++

6. left = 0, right = 5, count = 2，进入循环

   in=C，++hash2[in]=2，hash1[in]=2，count++，count=3

   count == kinds，进入while循环

   right - left + 1 < minlen，进入if

   minlen = right - left + 1; minlen=5-0+1=6
begin = left; begin=0

   char out = s[left++]; out=s[0]=A，left=1

   hash2[out]-- == hash1[out] == 3

   count--; count=2

   right++

7. left = 1, right = 6, count = 2，进入循环

   后面的过程一样，就不多赘述了。