力扣438:找到字符串中所有的字母异位词

题目

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

思路

我们先不看异位词这个条件，如何在字符串s中找到字符串p。我们可以构造一个和字符串p相同长度的窗口并且让这个窗口一位一位的进行移动例如字符串p的长度是3那么最开始窗口就是[0,1,2]，移动一位变成[1,2,3]这样循环往复。在每次移动之前我们都对这个窗口进行判断，判断窗口内的子串是否和字符串p相同。
那么这道题不也是一样的思路吗只是从判断是否相同变成了判断是否是异位词。那么重点就是如何判断是异位词，如果两个字符串互为异位词那么他们的共性是什么？拥有的字符数量是相同的字符也是相同的，所以我们可以分别创建一个26个字母的数组用来存储窗口和字符串p的字符数量，只要两个数组相同就说明是异位词。

代码

class Solution {
public:vector<int> findAnagrams(string s, string p) {int ssize = s.size();int psize = p.size();vector<int> res;// 如果s字符串还没p字符串长那就没有答案if (ssize < psize) {return res;}// 创建两个数组来存储// 两个字符串每个字符的数量vector<int> schar(26);vector<int> pchar(26);// 构造和字符串p相同长度的滑动窗口for (int i = 0; i < psize; i++) {schar[s[i] - 'a']++;pchar[p[i] - 'a']++;}if (schar == pchar) {res.push_back(0);}for (int i = 0; i < ssize - psize; i++) {// 进行滑动schar[s[i] - 'a']--;schar[s[i + psize] - 'a']++;if (schar == pchar) {res.push_back(i + 1);}}return res;}
};