题目链接
https://leetcode-cn.com/problems/minimum-window-substring/
题目
给你一个字符串?
s?、一个字符串?t?。返回?s?中涵盖?t?所有字符的最小子串。如果?s?中不存在涵盖?t?所有字符的子串，则返回空字符串?""?。
注意：
- 对于?
t?中重复字符，我们寻找的子字符串中该字符数量必须不少于?t?中该字符数量。 - 如果?
s?中存在这样的子串，我们保证它是唯一的答案。
示例
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"示例 2：
输入：s = "a", t = "a"
输出："a"示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示
1 <= s.length, t.length <= 105s?和?t?由英文字母组成
思路
解决这个题目，可以先看一道类似的简单一点的题：Leetcode-3：无重复字符的最长子串
这类题目，最优解应该就是滑动窗口法。一开始打算用一个哈希表储存字符串t里需要的各个字符的个数，一个哈希表储存当前滑动窗口里每个元素的个数。后来一想，对于出现在了滑动窗口里的而没有出现在字符串t里面的字符，没必要储存在哈希表中，因为我们压根不需要这些字符，直接忽略即可。另外，一开始打算建立两个哈希表，发现这也不是必要的，我们只要用一个哈希表储存字符串t里的各个字符的个数，也就是我们需要的字符个数即可，这也等于目前滑动窗口里我们需要的字符还缺少的个数。每当有个我们需要的字符进入滑动窗口，在哈希表里把这个字符需要的个数-1即可，反之+1。如果对于我们需要字符，还缺少的个数全都=0了，就说明这个滑动窗口（即当前的这个子串）已经满足要求。
首先我们遍历字符串t，t中的元素就是我们需要的元素，用一个哈希表记录每个元素以及各自需要的个数。
对于滑动窗口，我们首先定义滑动窗口的左端left和右端right，起始位置都为0和-1，对于left的移动，不需要一步一步移，当left的下一个元素不是我们需要的元素时，这个位置可以直接跳过，直到遇到我们需要的元素。这里需要注意，如果是第一次移动，要把left对应的元素在哈希表里还缺少的个数-1，并且让right从当前这个left开始遍历，而从第二次开始就不需要以上操作了，因为right肯定已经跑到了left后面，left遍历过的元素right已经遍历过了。
而每次遍历right一直往右移动直到滑动窗口（当前子串）满足要求或者到达s字符串尾部。
对于每个left，当right一直右移到滑动窗口满足要求或者right到了尾部时，这个left位置的寻找就结束了。这时候如果滑动窗口满足题目要求，且对应的字符串长度缩小了，则记录此时的left、right位置（用于输出结果字符串）。
在下一轮遍历开始前，也就是left下一次移动前，这个left指向的元素要踢出滑动窗口了，所以要把这个元素对应还缺少的元素数量+1。
最后，当所有的遍历结束（left遍历完所有位置），我们还需要判断在所有的遍历中存不存在这样一个满足要求的子串，如果一个都没，则返回空串，如果有的话则返回这个最小子串。
C++ Code
class Solution {
public:
bool match(unordered_map<char,int> map)
{
for(auto a:map)
{
if(a.second>0) return false;
}
return true;
}
string minWindow(string s, string t) {
unordered_map<char,int> map;//记录当前滑动窗口中缺失t字符串中各字符的个数
for(char ch:t)
{
map[ch]++;
}
int min_len=10e5,min_left=0,min_right=0;//最小子串长度及其相应左右下标
int left=0, right=-1; //当前滑动窗口的左右下标
for(left;left<s.size();left++)
{
//left不为需要的字符右移
while(left<s.size()&&map.find(s[left]) == map.end() )
{
left++;
}
//第一个遇到的left加入进滑动窗口 哈希表里对应需要的个数-1
//后面遇到的不需要-1，因为在right遍历到这的时候已经-1了
if(right==-1)
{
map[s[left]]--;
right=left;
}
//对右下标进行处理
while(right<s.size()-1 && match(map)==false ) //当前滑动窗口（子串）还不满足要求
{
right++; //right右移
if( map.find(s[right])!= map.end() )//如果right是我们需要的元素该元素缺失个数-1
{
map[s[right]]--;
}
}
//遍历完了 如果滑动窗口满足要求 且min_len减小更新min_len、min_left、min_right
if( match(map)==true && right-left+1<min_len)
{
min_len=right-left+1;
min_left=left;
min_right=right;
}
map[s[left]]++; //当前左元素踢出滑动窗口 对应哈希表里需要的个数+1
}
if(min_len!=10e5) //存在最小子串
{
string S;
for(int i=min_left;i<=min_right;i++)
{
S+=s[i];
}
return S;
}
else return "";
}
};
int main()
{
Solution S;
string s = "ADOBECODEBANC", t = "ABC";
string a=S.minWindow(s,t);
cout<<a<<endl;
system("pause");
return 0;
}结果
居然超时了，还需要对其进行改进,一样的思路，换成下面的就能通过。
?C++ Code
class Solution {
public:
unordered_map <char, int> ori, cnt;
bool check() {
for (const auto &p: ori) {
if (cnt[p.first] < p.second) {
return false;
}
}
return true;
}
string minWindow(string s, string t) {
for (const auto &c: t) {
++ori[c];
}
int l = 0, r = -1;
int len = INT_MAX, ansL = -1, ansR = -1;
while (r < int(s.size())) {
if (ori.find(s[++r]) != ori.end()) {
++cnt[s[r]];
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
}
if (ori.find(s[l]) != ori.end()) {
--cnt[s[l]];
}
++l;
}
}
return ansL == -1 ? string() : s.substr(ansL, len);
}
};
/*
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/