C++算法
滑动窗口算法解析：串联所有单词的子串与最小覆盖子串
滑动窗口算法解决串联所有单词的子串与最小覆盖子串问题。通过哈希表统计单词频次或字符频次，利用双指针维护窗口状态。串联所有单词的子串需处理单词长度步长，最小覆盖子串需动态调整窗口大小满足字符需求。提供 C++ 代码实现及详细流程解析，涵盖边界条件判断与优化策略。
滑动窗口算法解决串联所有单词的子串与最小覆盖子串问题。通过哈希表统计单词频次或字符频次，利用双指针维护窗口状态。串联所有单词的子串需处理单词长度步长，最小覆盖子串需动态调整窗口大小满足字符需求。提供 C++ 代码实现及详细流程解析，涵盖边界条件判断与优化策略。
有以下几点不同：
hash<string,int>class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
// 解法：滑动窗口 + 哈希表 (容器)
vector<int> ret;
unordered_map<string, int> hash1; // 统计 words 中所有单词出现的频次
for(auto e : words) {
hash1[e]++;
}
int len = words[0].size(); // len 为 words 中每个字符串的长度
int m = words.size(); // m 为 words 的长度
int left = 0;
int right = 0;
for(int i = 0; i < len; i++) {
unordered_map<string, int> hash2; // 存放 s 中的子串
int count = 0; // 统计窗口中'有效字符串'的个数
left = i;
// 注意 size_t 类型与 int 类型运算时的转换问题
for(right = i; right + len <= s.size(); right += len) {
string str1 = s.substr(right, len);
hash2[str1]++; // 进窗口
if(hash2[str1] <= hash1[str1]) {
count++;
}
if(right - left + 1 > len * m) { // 判断
string str2 = s.substr(left, len);
if(hash2[str2] <= hash1[str2]) {
count--;
}
hash2[str2]--; // 出窗口
left += len;
}
if(count == m) { // 更新结果
ret.push_back(left);
}
}
}
return ret;
}
};
研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。
如何判断当前窗口的所有字符是符合要求的呢？
主函数中：
class Solution {
public:
string minWindow(string s, string t) {
// 优化：数组模拟实现哈希表，count 标记'有效字符'的种类
int hash1[128] = { 0 }; // 统计字符串 t 中每个字符出现的频次
int kinds = 0; // 统计'有效字符'有多少种
for(auto c : t) {
if(hash1[c]++ == 0) {
kinds++;
}
}
int left = 0;
int right = 0;
int count = 0;
int min_len = s.size() + 1;
int begin = -1;
string ret;
int hash2[128] = { 0 };
for(right = 0; right < s.size(); right++) {
hash2[s[right]]++; // 进窗口
if(hash2[s[right]] == hash1[s[right]]) {
count++;
}
while(count == kinds) { // 判断
if(min_len > right - left + 1) { // 更新结果
min_len = right - left + 1;
begin = left;
}
if(hash2[s[left]] == hash1[s[left]]) {
count--;
}
hash2[s[left]]--; // 出窗口
left++;
}
}
(begin != ) {
ret = s.(begin, min_len);
}
ret;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online