网站建设规划面试技巧,网站改版 英文,广告策划书包括什么内容,wordpress 热门 tags文章目录 题目描述算法原理滑动窗口哈希表 代码实现 题目描述
题目链接#xff1a;438.找到字符串中所有字母异位词
算法原理
滑动窗口哈希表
因为字符串p的异位词的⻓度⼀定与字符串p 的⻓度相同#xff0c;所以我们可以在字符串s 中构造⼀个⻓度为与字符串p的⻓度相同… 文章目录 题目描述算法原理滑动窗口哈希表 代码实现 题目描述
题目链接438.找到字符串中所有字母异位词
算法原理
滑动窗口哈希表
因为字符串p的异位词的⻓度⼀定与字符串p 的⻓度相同所以我们可以在字符串s 中构造⼀个⻓度为与字符串p的⻓度相同的滑动窗⼝并在滑动中维护窗⼝中每种字⺟的数量当窗⼝中每种字⺟的数量与字符串p 中每种字⺟的数量相同时则说明当前窗⼝为字符串p的异位词因此可以⽤两个⼤⼩为26 的数组来模拟哈希表⼀个来保存s 中的⼦串每个字符出现的个数另⼀个来保存p中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
代码实现
class Solution {
public:vectorint findAnagrams(string s, string p) {int hash1[26] { 0 };//统计字符串p中每个字符出现的个数for(auto ch : p)hash1[ch - a];int hash2[26] { 0 };//统计窗口里面每一个字符出现的个数vectorint res;for(int left 0,right 0,count 0;right s.size();right)//1.控制窗口{char in s[right];if(hash2[in - a] hash1[in - a])count;//2.进窗口维护countwhile(right - left 1 p.size())//3.判断{char out s[left];if(hash2[out - a]-- hash1[out - a])count--;//维护count出窗口}if(count p.size()) res.push_back(left);//更新结果}return res;}
};
