题目1：30. 串联所有单词的子串（困难）
思路分析：
整体思路和异位词那题一样，只是把一个字母，变成了string，算法一样的。但需要错位跑几次，才能跑全
思路1：滑动窗口+哈希map
代码实现：
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { unordered_map<string, int> hash1; for (auto s : words) hash1[s]++; vector<int> ret; int n = s.size(), len = words[0].size(), m = words.size(); for (int i = 0; i < len; i++) { unordered_map<string, int> hash2; for (int left = i , right =i, count = 0; right+len <= n;right += len) { //进窗口+维护count string in = s.substr(right, len); hash2[in]++; if (hash1.count(in)&&hash2[in] <= hash1[in]) count++; //判断 if (right-left+1>len*m) { //出窗口+维护count string out = s.substr(left, len); if (hash1.count(out)&&hash2[out] <= hash1[out]) count--; hash2[out]--; left += len; } //更新结果 if (count == m) ret.push_back(left); } } return ret; } };
题目2：LCR 017.最小覆盖子串
思路分析
思路1：滑动窗口+哈希表
class Solution { public: string minWindow(string s, string t) { int hash1[60]={0}; //统计t中字母个数 for(auto ch:t) hash1[ch-'A']++; int hash2[60]={0}; int n=s.size(),m=t.size(); int minlen=INT_MAX,begin=-1; //返回值 for(int left=0,right=0,count=0;right<n;right++) { //进窗口，没条件都进 char in=s[right]; hash2[in-'A']++; //维护count 记录有效字母个数 if(hash2[in-'A']<=hash1[in-'A']) count++; while(count==m) //判断 { //出窗口+维护count char out=s[left]; if(hash2[out-'A']<=hash1[out-'A']) { if(right-left+1<minlen) { minlen=right-left+1; begin=left; } count--; } hash2[out - 'A']--; left++; } } if(begin==-1) return ""; else return s.substr(begin,minlen); } };
