438 找到字符串中所有字母异位词

题目给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:输入: s “cbaebabacd”, p “abc”输出: [0,6]解释:起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。示例 2:输入: s “abab”, p “ab”输出: [0,1,2]解释:起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。思路使用哈希表滑动窗口先把p存在map里面key是charvalue是频率。然后用两个指针维护一个跟p相同大小的窗口窗口里面的元素也放在哈希表里面。当窗口一样大的时候检查两个哈希表是否相同然后l1移动到下一个窗口。在检查两个哈希表是否相同的时候有两种方法逐个对比哈希表p对比是否相同。用一个have维护两个哈希表里面相同元素的数量。前者复杂度是onm m是p的长度后者复杂度是on后者需要细心。注意点在在右指针右移后检测右边界的时候需要检测右边界元素和p哈希表里的频率是否相等不是大于等于避免have误加在移动左指针之前检测左边界的元素是否跟p哈希表频率相等处理完have是否减少然后再移动左指针避免have误减代码classSolution{public:vectorintfindAnagrams(string s,string p){vectorintres;unordered_mapchar,intneed;unordered_mapchar,intmp;intl0,r0,lenPp.size();for(autoit:p){need[it];}intneedsizeneed.size(),have0;while(rs.size()){if(need.count(s[r])){mp[s[r]];if(need[s[r]]mp[s[r]]){have;}}if(r-l1lenP){if(haveneedsize){res.push_back(l);}// 注意这里应该先提前判断左边界的字符是不是不满足have条件,再移动左边界if(need.count(s[l])){if(mp[s[l]]need[s[l]]){have--;}}mp[s[l]]--;l;}r;}returnres;}};感谢 感谢华南溜达虎 力扣hot 100这道题目要优化为o(n)需要注意的地方有点多,写了半天,流汗ing还有一道很像的题目76最小覆盖子串都挺难绷