力扣hot100 C++(滑动窗口自用)

思路:右指针始终要向右移动遍历字符,若滑动窗口中没有与右指针指向字符重复,右指针指向字符加入滑动窗口;当滑动窗口中出现重复元素时,滑动窗口从左指针开始删除元素且左指针要右移动直到没有重复字符的位置停止;每一次滑动窗口的长度都要与上一次滑动窗口的大小比较,只保留最大的滑动窗口。对应值就是不含有重复字符的最长子串的长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty()) return 0;
int n=s.length();
unordered_set<int>window;
int ans=1;
int left=0;
int right;
for(right=0;right<n;right++)
{
while(window.find(s[right])!=window.end())
{
window.erase(s[left]);
left++;
}
window.insert(s[right]);
ans=max(ans,(int)window.size());
}
return ans;
}
};

思路:将p字符串中对应字符的出现次数,滑动窗口大小固定为p的长度;滑动窗口从s字符串第一个字符位置开始,在滑动窗口内字符出现次数对应数组与p字符出现次数对应数组比较,若一样则记录当前滑动窗口的左指针,滑动窗口右移;若不一样,滑动窗口的左右指针都右移一位;直到滑动窗口右指针指针到s字符串最后一位字符;最后记录的滑动窗口的左指针集合就是结果;
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int len_p=p.length();
int len_s=s.length();
vector<int>cnt_p(26,0);
vector<int>result;
for(char c_p:p)
{
cnt_p[c_p-'a']++;
}
vector<int>cnt_w(26,0);
for(int right=0;right<len_s;right++)
{
cnt_w[s[right]-'a']++;
int left=right-len_p+1;//当前窗口的左指针
if(right>=len_p)//右指针位置比p长度大,滑动窗口左指针要开始滑动
{
cnt_w[s[left-1]-'a']--;//当前窗口的左指针位置右移动,左指针前面元素对应次数减少一次
}
if(cnt_w==cnt_p)//数组一致
result.push_back(left);
}
return result;
}
};
更多推荐
所有评论(0)