水果成篮
题目描述： 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。你想要尽可能多地收集水果，但是有一些规则：
- 你有两个篮子，每个篮子只能装一种类型的水果，篮子的容量无限制。
- 你可以选择任意一棵树开始采摘，但必须从这棵树开始依次向右采摘每棵树上的水果。
- 一旦遇到某棵树上的水果不符合篮子中的水果种类，你必须停止采摘。 返回你能采摘的最多的水果数量。
解题思路
解法：滑动窗口 + 哈希
根据题目要求，所求问题其实就是找一段最多只含两个不同元素的最长子区间，我们使用滑动窗口 + 哈希解决。
有一点值得注意，fruits[i] 是第 i 棵树上的水果种类，不是种类数。
具体过程如下：
- 初始化哈希表 hash，左右指针 left 和 right，记录结果的变量 ret。
- right 向右遍历数组，将 right 位置的水果加入哈希表，统计频次。
- 如果哈希表的大小超过 2，让 left++并同时更新哈希表，直至哈希表的大小不超过 2。
- 更新结果 ret。
- 重复上述过程，直到 right 遍历完数组。
代码实现
1. 使用 unordered_map 作为 hash 表
class Solution {
public:
int totalFruit(vector<int>& fruits) {
// 统计滑动窗口内水果的种类和数量
unordered_map<int, int> hash;
int n = fruits.size(), ret = 0;
for(int left = 0, right = 0; right < n; right++) {
// 进窗口，将水果加入 hash 表
hash[fruits[right]]++;
// 若水果种类超过 2，收缩窗口直到种类不超过 2
while(hash.size() > 2) {
hash[fruits[left]]--;
if(hash[fruits[left]] == 0) hash.erase(fruits[left]);
left++;
}
// 更新结果
ret = max(ret, right - left + 1);
}
return ret;
}
};
2. 使用数组模拟 hash 表
题目其实有提到 fruits[i] 的范围，所以我们不必真的使用 unordered_map 作为 hash 表，使用数组模拟即可，这样虽然会浪费空间，但是提高了效率。
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int hash[100000] = { 0 };
// cnt 用于统计 hash 表的水果的种类个数
int n = fruits.size(), ret = 0, cnt = 0;
for(int left = 0, right = 0; right < n; right++) {
hash[fruits[right]]++;
if(hash[fruits[right]] == 1) cnt++;
while(cnt > 2) {
hash[fruits[left]]--;
if(hash[fruits[left++]] == 0) cnt--;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
时间复杂度：O(n)
空间复杂度：O(n)
找到字符串中所有字母异位词
题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。顺序可以不考虑。
异位词是指由相同字母重排列形成的字符串（包括相同的字符串）。
解题思路
解法：滑动窗口 + 哈希
因为字符串 p 的异位词的长度一定于字符串 p 的长度相等，所以我们可以在字符串 s 中使用与字符串 p 等长度的滑动窗口来求解。
我们可以使用两个大小为 26 的数组来模拟哈希表，用于统计窗口内的字母频次和字符串 s 的字母频次，当比较得到两个哈希表相等时，说明滑动窗口中每种字母的数量与字符 p 每种字母的数量相同，窗口内的字符是字符 p 的一个异位词，此时记录窗口起始索引。
具体过程如下：
- 初始化 left 和 right 指针来维护滑动窗口，两个大小为 26 的数组 hash1 和 hash2 来模拟哈希表，记录字符串 p 的字母频次和窗口字母频次。
- right 向右遍历数组****right 位置的字母入窗口，将其加入哈希表。当滑动窗口长度大于字符串 p 的长度时，left++，将窗口左侧字母移除同时更新其在哈希表的频次。
- 更新结果，当 hash1 与 hash2 相等时，记录窗口起始索引。
注意：判断两个 hash 表是否相等的时间复杂度较高，效率较低。故我们要优化更新结果的判断条件（两个哈希表相等），我们可以来使用一个变量 cnt 记录窗口内的字母相较于字符串 p 的有效字符的数量，并在入窗口和窗口时维护 cnt，这样更新结果时，只需判断 cnt 是否等于字符串 p 的长度就可以知道窗口字符是否是字符串 p 的异位词。
解释下有效字符的数量，其实就是让窗口的组成字母尽可能接近字符 p ，当有效字符的数量等于字符 p 的长度，就说明了窗口的字母频次与字符 p 的字母频次相等，这也是比较两个统计字母频次的哈希表相等的本质，cnt 间接完成了这个任务。
代码实现
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int n = s.size(), m = p.size();
// 统计 p 字符串中每个字母出现的个数
int hash1[26] = { 0 };
for(auto ch : p) hash1[ch - 'a']++;
// 统计窗口中每个字母出现的个数
int hash2[26] = { 0 };
// 统计窗口中有效字符的数量
int cnt = 0;
for(int left = 0, right = 0; right < n; right++) {
// 进窗口 + 维护 cnt
char in = s[right];
hash2[in - 'a']++;
if(hash2[in - 'a'] <= hash1[in - 'a']) cnt++;
// 窗口长度大于字符串 p 的长度，窗口左端字母出窗口，
// 并更新 cnt 和哈希表
if(right - left + 1 > m) {
char out = s[left++];
// 出窗口 + 维护 cnt
if(hash2[out - 'a'] <= hash1[out - 'a']) cnt--;
hash2[out - 'a']--;
}
// 更新结果
if(cnt == m) ret.push_back(left);
}
return ret;
}
};
时间复杂度：O(n)
空间复杂度：O(1)
串联所有单词的子串
题目描述：
给定一个字符串 s 和一个字符串数组 words，words 中所有字符串的长度相同。s 中的 串联子串 是指包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words=["ab","cd","ef"]，那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是串联子串，而 "acdbef" 不是串联子串，因为它不是 words 排列的连接。
返回所有串联子串在 s 中的开始索引，顺序可以不考虑。
解题思路
解法：滑动窗口 + 哈希表
这道题就是找到字符串中所有字母异位词的升级版，从原来处理单个字符变成了处理单个单词，我们只需要将 words 的单词看成单个字母就行了，然后用滑动窗口 + 哈希表解决。
具体过程：
- 用哈希表 hash1 记录 words 中每个单词的频次。
- 遍历字符串 s，并用哈希表 hash2 来维护滑动窗口内的单词频次，注意每次增加窗口的大小为单词的长度。
- 当窗口大小大于所有单词的总长度时，出窗口和更新 hash2。
- 当 hash1 和 hash2 两个哈希表相等时，更新结果。
判断两个哈希表是否相等消耗较大，用 count 来优化，**count 统计滑动窗口内有效单词的个数。**当 count 与 words 的单词个数相等时，说明找到了符合条件的一个窗口。
代码实现
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
unordered_map<string, int> hash1;
for(auto& e : words) hash1[e]++;
int len = words[0].size(), m = words.size(), n = s.size();
// 执行 len 次滑动窗口
for(int i = 0; i < len; ++i) {
unordered_map<string, int> hash2;
for(int left = i, right = i, count = 0; right <= n - len; right += len) {
// 进窗口 + 维护 count
string in(s.begin() + right, s.begin() + right + len);
hash2[in]++;
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
// 判断 + 出窗口 + 维护 count
if(right - left + 1 > m * len) {
string out(s.begin() + left, s.begin() + left + len);
if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += len;
}
// 更新结果
if(count == m) ret.push_back(left);
}
}
return ret;
}
};
- 执行 len 次滑动窗口（len 是单词长度）：由 s 字符串的长度不一定是单词长度的整数倍，需要执行 len 滑动窗口来保证答案的完整性。
- 注意 right 的范围，right 最后一次执行循环的位置应该是在 n - len 处。
时间复杂度：O( n * len)，其中 n 是字符串 s 的长度，需要 len 次滑动窗口，每次遍历一次 s。
空间复杂度：O(m * len)，m 是单词个数，每次滑动窗口都需要用一个哈希表来存储单词频次。
最小覆盖子串
题目描述：
给你一个字符串 s 和一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在这样的子串，则返回空字符串 ""。
注意：
- 对于
t中重复的字符，最小子串中该字符数量必须不少于t中的字符数量。 - 如果存在这样的子串，答案是唯一的。
解题思路
解法：滑动窗口 + 哈希
根据题目，我们直接根据暴力解法来优化，就得到滑动窗口 + 哈希的解题方法。
具体过程如下：
- 利哈希表 hash1 来统计字符串 t 中每个字符出现的频次。
- 使用滑动窗口遍历字符串 s，并用哈希表 hash2 来统计窗口中字符频次。
- 当窗口的字符频次满足要求时，更新结果，然后收缩窗口，直到窗口字符频次不满足要求。
注意：这里判断窗口的字符频次满足要求不是判断两个哈希表是否相等，而是 hash1 的字符频次要完整的出现在 hash2 中，hash1 中可以出现除字符串 t 中的字符以外的字符频次。也就是说，窗口内只要完整出现字符串 t 的所有字符即可（字符种类及其对应的频次）。
我们这里还是利用 count 来完成判断，这里的 count 统计的时有效字符的种类，只有 t 中的单个字符在窗口内出现的频次与在 t 中完全一样，count 才自增 1，同理，频次不相等时就自减 1，当 count 与 t 中字符种类数相同时，说明找到一个符合条件的覆盖字串，更新结果。
代码实现
class Solution {
public:
string minWindow(string s, string t) {
string ret;
// hash1 统计 t 字符频次和计算 hash1 的大小，hash1size 统计 t 的字符种类
int hash1[128] = { 0 }, hash1size = 0;
for(auto e : t) if(hash1[e]++ == 0) hash1size++;
// hash2 统计窗口字符频次
int hash2[128] = { 0 };
int len = INT_MAX, start = 0;
// count 统计有效字符的种类
for(int left = 0, right = 0, count = 0; right < s.size(); right++) {
// 进窗口 + 维护 count
char in = s[right];
if(++hash2[in] == hash1[in]) count++;
// 判断
while(count == hash1size) {
// 更新结果
if(right - left + 1 < len) {
len = right - left + 1;
start = left;
}
// 出窗口 + 维护 count
char out = s[left++];
if(hash2[out]-- == hash1[out]) count--;
}
}
ret = len == INT_MAX ? "" : s.substr(start, len);
return ret;
}
};
时间复杂度：O(n)
空间复杂度：O(1)
