区块链app开发价格seo培训学院

给定两个字符串s和t， 找到s的一个子串，使得t的每个字符都出现在子串中，求最短的子串

由于要每个字符出现，所以顺序其实没有关系
因此我们可以定义一个map，统计t中字符出现次数
然后在s中慢慢挪动滑动窗口，如果符合要求就缩短滑动窗口，直到不符合，然后继续移动

class Solution {
public:string minWindow(string s, string t) {int ans = -1, ans_len = -1, n = s.size(), m = t.size();if(n < m)return "";unordered_map<char, int> mp;for(char& c:t)++mp[c];int cnt = mp.size(), pre = 0;for(int i = 0; i < n; ++i){auto it = mp.find(s[i]);if(it == mp.end())continue;--it->second;if(it->second == 0){--cnt;if(cnt == 0){if(m == 1)return t;if(ans_len == -1 || i - pre + 1 < ans_len){ans_len = i - pre + 1;ans = pre;}while(pre < i){auto it2 = mp.find(s[pre]);++pre;if(it2 == mp.end()){if(i - pre + 1 < ans_len){ans_len = i - pre + 1;ans = pre;}continue;}++it2->second;if(it2->second == 1){++cnt;break;}else{if(i - pre + 1 < ans_len){ans_len = i - pre + 1;ans = pre;}}}while(pre < i){auto it2 = mp.find(s[pre]);if(it2 == mp.end()){++pre;continue;}else{break;}}}}}if(ans == -1)return "";return s.substr(ans, ans_len);}
};