LeetCode 热题 100——找到字符串中所有字母异位词(滑动窗口)

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

该题目的意思简而言之就是说，从s字符串中寻找与p字符串含有相同字符(次数和种类均相同)的子串，并且将他们的首字符下标集合进数组中进行返回。

滑动窗口解法(未优化版本)

分析完该题目可以发现，该题是一个大小不变的滑动窗口题目。窗口大小一直为p字符串的大小，并且我们出窗口和进窗口的大小是相同的，就相当于我们拿着一个窗口在s字符串上去滑动，直到我们找到合适的子串。

如以下动图所示：

 代码如下(含详细注释)

// 该题是一个大小固定的滑动窗口题目
class Solution 
{
public:// 设计一个函数来检查两个哈希表是否相等bool check_hash(int hash1[],int hash2[]){for(int i=0;i<26;i++)if(hash1[i]!=hash2[i]) return false;return true;}vector<int> findAnagrams(string s, string p) {int p_hash[26]={0};int s_hash[26]={0};int ns=s.size();int np=p.size();// 将p字符串中的字符插入到p_hash中for(auto&e:p) p_hash[e-'a']++;vector<int> ret;for(int left=0,right=0;right<ns;right++){// 直接将right对应位置字符进行入哈希表char in=s[right];s_hash[in-'a']++;// 如果right-left+1>np说明已经超过我们滑动窗口的大小了if(right-left+1>np){// 直接从左边进行出窗口char out=s[left++];s_hash[out-'a']--;}// 检查是否符合条件(两个哈希表是否相等)if(check_hash(s_hash,p_hash))// 相等就把该字符串最左边字符的下标入ret数组中ret.push_back(left);}return ret;}
};

滑动窗口(优化版本)

该题只存放了小写字母，因此我们检查两个哈希表其实时间复杂度是非常低的，倘若存入的不止是小写字母，那么我们检查的这一步操作时间复杂度就会非常高，并且检查的这一步操作每一次滑动的时候我们都要进行检测，因此我们可以使用一个count来记录s_hash哈希表中有效字符(存在的字符是p_hash中的字符)的数量，进窗口的时候我们将count++，出窗口的时候我们将count--。

代码如下(含详细注释)

// 优化版本
// 该题是一个大小固定的滑动窗口题目
class Solution 
{
public:vector<int> findAnagrams(string s, string p) {int p_hash[26]={0};int s_hash[26]={0};int ns=s.size();int np=p.size();// 将p字符串中的字符插入到p_hash中for(auto&e:p) p_hash[e-'a']++;vector<int> ret;for(int left=0,right=0,count=0;right<ns;right++){char in=s[right];// 当前字符插入s_hash之后// 如果s_hash中该字符对应的次数<=p_hash[in-'a']// 说明若不是该字符次数在s_hash中的次数与p_hash中的次数一样// 那就是插入之后还比p_hash中的次数少// 无论哪种情况均能说明该字符存在于p_hash中 符合我们要找的字符// 因此count++ 也就是统计的是s_hash中的有效字符数量if(++s_hash[in-'a']<=p_hash[in-'a']) count++;// 如果right-left+1>np说明已经超过我们滑动窗口的大小了if(right-left+1>np){char out=s[left++];// 这一步同理上一步 // 当我们将该字符移除之前该字符次数在s_hash中小于p_hash// 说明该字符是有效字符// 就算该字符不是我们要的有效字符 仍然可以出窗口 只不过count不进行--操作罢了if(s_hash[out-'a']--<=p_hash[out-'a']) count--;}// 如果此时count==np说明当前情况完全满足我们的要求 加入该结果即可if(count==np)ret.push_back(left);}return ret;}
};