题意大致是,给定两个字符串,s 和 p
其中 要在s 中找到由p的元素组成的子字符串,记录子字符串首地址
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int m = s.size(), n = p.size();
if(m < n)return {};
vector<int> hashTable(26);
for(auto ch : p){
hashTable[ch - 'a']++;
}
vector<int> ret;
/*
手动移动滑动窗口右边界,如果是新元素循环循环移动左边界,直到找到右边的那个元素
如果串口长度于p的长度一致,达成条件
*/
for(int l = 0, r = 0; r < m; ++r){
hashTable[s[r] - 'a']--;
while(hashTable[s[r] - 'a'] < 0){
hashTable[s[l] - 'a']++;
l++;
}
if(r - l + 1 == n){
ret.push_back(l);
}
}
return ret;
}
};
其实很容易想到滑动窗口
这道题解的思路是,先把p的所有元素记录下来,然后开始遍历滑动串口的右边界,直接hashTable[s[r]]–;
如果其值>= 0 说明遍历的滑动窗口(s的子串)有p 的元素,不管 ,继续移动右窗口,直到滑出边界
如果 < 0 说明 新元素,此时右边界不能动,动左边界,左边界怎么动呢?就是左边界不断加元素,不断右移,最后把新元素添加进去了。
在窗口滑动的过程中,如果满足 r - l + 1 == n 说明找到了一个满足 p 的子字符串。
//还有一个
// 思想是一样的,但是看着会比较啰嗦
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> mp;
vector<int> result;
int s_len = s.size(), p_len = p.size();
for(auto & c : p){
mp[c]++;
}
int left = 0, right = 0, count = p_len;
// 初始化滑动窗口
while(right < p_len){
if(mp.count(s[right]) > 0 && mp[s[right]] > 0){
count--;
}
mp[s[right]]--;
right++;
}
if(count == 0){
result.push_back(left);
}
//移动滑动窗口
while(right < s_len){
if(mp.count(s[left]) > 0 && mp[s[left]] >= 0){
count++;
}
mp[s[left]]++;
left++;
if(mp.count(s[right]) > 0 && mp[s[right]] > 0){
count--;
}
mp[s[right]]--;
right++;
if(count == 0){
result.push_back(left);
}
}
return result;
}
};