水果成篮
题目解析
本题要求从一个数组里面选取两个数组成的最长子数组。暴力解法时间复杂度为 O(N^2)，滑动窗口可优化至 O(N)。
算法原理
引入变量判断种类，数的范围是 10 的五次方，所以引入的 hash 表为 100001。固定三部曲：进窗口的时候维护 kinds，如果最开始为 0，那么没有该水果种类，就可以直接 kinds++。判断条件如果 kinds 大于水果种类的话，就出窗口，即 left++。同时要维护 kinds，如果哈希表的映射变为 0 了，那么 kinds 就--。
算法编写
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int hash[100001] = { 0 };
int ans = 0, kinds = 0;
for(int left = 0, right = 0; right < fruits.size(); right++) {
// 进窗口
if(hash[fruits[right]]++ == 0) kinds++;
// 判断
while(kinds > 2) {
if(--hash[fruits[left++]] == 0) kinds--;
}
// 更新结果
ans = max(ans, right - left + 1);
}
return ans;
}
};
此时的时间复杂度是 O(N)。
找到字符串中所有字符异位词
题目解析
题目要求返回所有异位词的起始索引。异位词指将原字符串进行排列组合之后组成的字符串。判断某个子串是不是异位词，可以使用哈希表映射统计字符频次。
算法原理
判定为滑动窗口，使用一个连续的区间和另一个连续的区间进行比较。进窗口使用 right 指针，当 right 和 left 的区间长度大于了目标字符串的长度时，需要出窗口，左边出窗口即可。
使用哈希映射，统计目标字符串中字符出现的频次。第一个哈希表用来计算目标字符串出现的字母频次，第二个哈希表用来计算左右区间出现的字符频次，最后比较两个哈希表是否相等。
出窗口的时候，如果目标字符的频次变成了 0，就删除该元素。此时两个哈希表判断是否相等，相等更新结果。
算法编写
基于 unordered_map 的实现：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
unordered_map<char,int> hash1;
unordered_map<char,int> hash2;
for(auto e : p) hash1[e]++;
for(int left = 0, right = 0; right < s.size(); right++) {
hash2[s[right]]++;
if((right - left + 1) > p.size()) {
char out = s[left];
if(--hash2[out] == 0) hash2.erase(out);
left++;
}
if(hash1 == hash2) ans.push_back(left);
}
return ans;
}
};
基于数组优化的实现：
由于字母只有 26 个且都是小写，可以使用数组模拟哈希表。引入变量 kinds 统计有效字符的个数。对于异位词来说，有效字符的个数就是相当于排序之后的任意字符串的一个一致结果。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int hash1[26];
int hash2[26];
int kinds = 0;
memset(hash1, 0, sizeof(hash1));
memset(hash2, 0, sizeof(hash2));
for(auto e : p) hash1[e - 'a']++;
for(int left = 0, right = 0; right < s.size(); right++) {
if(++hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) kinds++;
if(right - left + 1 > p.size()) {
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a']) kinds--;
}
if(kinds == p.size()) ans.push_back(left);
}
return ans;
}
};
运行时间显著提升。