找到字符串中所以字母异位词 --- 滑动窗口

目录

一：题目

二：算法原理 

三：代码实现

---

一：题目

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

二：算法原理 

三：代码实现

版本一：无cont优化

class Solution {
public:vector<int> findAnagrams(string s, string p){vector<int> ret;unordered_map<int, int> hash1;unordered_map<int, int> hash2;int len = p.size();for (int i = 0; i < p.size(); i++){hash1[p[i]]++;}int left = 0, right = len - 1;for (int i = left; i <= right; i++){hash2[s[i]]++;}while (right < s.size()){if (hash1 == hash2)ret.push_back(left);hash2[s[left]]--;if (hash2[s[left]] == 0){hash2.erase(s[left]);}left++;hash2[s[++right]]++;}return ret;}
};

版本二：cont优化

class Solution {
public:vector<int> findAnagrams(string s, string p){vector<int> ret;int hash1[26] = { 0 };//统计p中每一个字符出现的次数int hash2[26] = { 0 };//统计窗口中每一个字符出现的个数for (int i = 0; i < p.size(); i++){hash1[p[i] - 'a']++;}for (int left = 0, right = 0, cont = 0; right < s.size(); right++){//进窗口hash2[s[right] - 'a']++;if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])cont++;//判断if ((right - left + 1) > p.size()){//出窗口if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a'])cont--;hash2[s[left++] - 'a']--;}//更新结果if (cont == p.size())ret.push_back(left);}return ret;}
};