利为汇网站建设/国内最新消息新闻

题目如下

给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

解题思路

思想：
1.数组滑动窗口长度为p串的长度，在s中不停滑动，满足要求就存头部索引值
2.字母只有26个用数组代替hashmap，key为1-26字母，value为串中字母出现的频次

解题代码

class Solution 
{
public:vector<int> findAnagrams(string s, string p) {vector<int> s_count(26), p_count(26), res;if (s.size() < p.size()){return res;//s一定比p长}int j = 0, i = 0;//先创建一个同p长度的字母频次库for (; i < p.size(); ++i){p_count[p[i] - 'a']++;s_count[s[i] - 'a']++;}//开始以p的长度在s中滑动，并每次检查是不是异位词（变位词）if (p_count == s_count){res.emplace_back(j);}for (; i < s.size(); ++i) {s_count[s[j++] - 'a']--;//滑动窗口每次踢除头部数字s_count[s[i] - 'a']++;//滑动窗口尾部加入数字if (p_count == s_count){res.emplace_back(j);}}return res;}
};