给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
创造不易，不喜勿喷，个人见解，有错误欢迎指点
看到题目的第一想法：一个大字符串(s)里面找小字符串(p)，并且没有顺序要求，首先考虑滑动窗口，我们定义窗口大小为小字符串的长度p_len，在大字符串(s)中移动滑动窗口，每次移动一个字符，每次移动之后，拿滑动窗口和p比较里面字符是否一致，不要求位置一样，这里比较如果要求位置一样那就简单，遍历两个字符串比较就可以了，但是现在位置可以不要求一样，那就需要用哈希表来辅助了，我们创建一个哈希表，将滑动窗口和p加入，然后比较两个哈希表是否一样即可
优化
我们之前每次都需要对滑动窗口和小字符串p创建哈希表，但是可以发现滑动窗口是变化的，但是小字符串p是不变的，那么我们就可以创建一次哈希表，保存p的值，然后反复和滑动窗口进行比较，这样子就可以减少对不变p进行反复操作
再优化
我们之前对小字符串p进行了优化，只对p进行了一次遍历，但是还是对s每一步都需要对滑动窗口进行哈希表转换，那么是不是有一种方法可以让减少对滑动窗口的哈希表转换了，或者不是每一步都需要去反复遍历整个滑动窗口，当然是有的，我们之前都是滑动窗口是不变的，那么我们引入双指针来维护这个滑动窗口，一个是窗口前指针，一个是窗口后。当访问元素是p中元素，并且这个元素还可以添加到滑动窗口中，即这个元素出现的次数小于p中该元素出现的次数，那么我们使窗口大小加1，并且使窗口前指针前进，添加新的元素，当访问元素不是p中元素，或者这个元素在滑动窗口中出现的次数大于了在p中出现的次数，那么我们就缩小窗口大小，因为这个窗口多了一个元素，我们使窗口的尾指针排出元素，排到什么为止，当然是把多的这个元素排出去为止。因为每个元素在p中出现的次数是一定的，我们控制的窗口大小又始终保存出现元素个数小于等于p中出现的次数，那么当窗口大小等于p的大小时，是不是就说明我们这个窗口是p的异位词了
你品！你细品！
拜拜结束！！！
喜欢就点个赞宝！！！
代码第一次
int strCmpn(char * s, char * p , int n , int p_len)
{
int * a = malloc(sizeof(int) * 26);//滑动窗口哈希表初始化为0
int * b = malloc(sizeof(int) * 26);//p哈希表初始化为0
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
int i = n;
int j = 0;
for(i,j; j < p_len; i++, j++)//对滑动窗口，p进行遍历赋值
{
int t_a = s[i] - 'a';
int t_b = p[j] - 'a';
a[t_a]++;
b[t_b]++;
}
int sum = 0;
for(j = 0; j < 26; j++)//相同返回sum为0，不相同返回不相同元素
{
sum += abs(a[j] - b[j]);
}
free(a);
free(b);
return sum;
}
int* findAnagrams(char * s, char * p, int* returnSize){
int i;
int p_len = strlen(p);
int s_len = strlen(s);
*returnSize=0;
if(s_len < p_len)
{
return NULL;
}
int * ans = malloc(sizeof(int) * 30000);
for(i = 0; i < s_len-p_len+1; i++)//移动滑动窗口
{
if(strCmpn(s, p, i, p_len) == 0)
{
ans[(*returnSize)++] = i;
}
}
return ans;
}
优化
int strCmpn(char * s, int * b , int n , int p_len)
{
int a[26] = {0};//滑动窗口哈希表初始化为0
int i = n;
for(i; i < p_len+n; i++)//对滑动窗口进行遍历赋值
{
a[s[i] - 'a']++;
}
int sum = 0;
for(i = 0; i < 26; i++)//相同返回sum为0，不相同返回不相同元素
{
sum += abs(a[i] - b[i]);
}
return sum;
}
int* findAnagrams(char * s, char * p, int* returnSize){
int i;
int p_len = strlen(p);
int s_len = strlen(s);
*returnSize=0;
if(s_len < p_len)
{
return NULL;
}
int b[26] = {0};//对p的哈希表初始化为0
for(i = 0; i < p_len; i++)//对p进行遍历赋值
{
b[p[i] - 'a']++;
}
int * ans = malloc(sizeof(int) * 30000);
for(i = 0; i < s_len-p_len+1; i++)//移动滑动窗口
{
if(strCmpn(s, b, i, p_len) == 0)
{
ans[(*returnSize)++] = i;
}
}
return ans;
}
再优化
int* findAnagrams(char * s, char * p, int* returnSize){
int i,j;
int p_len = strlen(p);
int s_len = strlen(s);
*returnSize=0;
if(s_len < p_len)
{
return NULL;
}
int a[26] = {0};
int b[26] = {0};
int len = 0;
for(i = 0; i < p_len; i++)//对p进行遍历赋值
{
b[p[i] - 'a']++;
}
int * ans = malloc(sizeof(int) * 30000);
for(i = 0, j = 0; i < s_len && j < s_len; )//移动滑动窗口
{
if(a[s[i] - 'a'] < b[s[i] - 'a'])//当前位置的字符是p中元素，并且还可以再添加起码一个
{
a[s[i] - 'a']++;//
len++;//滑动窗口大小加一
i++;//进行向滑动窗口添加元素
if(len == p_len)//滑动窗口的长度正好等于p的长度，保存i的初始值
{
ans[(*returnSize)++] = i-p_len; //i的初始值等于当前位置-滑动窗口大小+1
}
}
else//当前元素不是p中元素或者是p中元素，但是这个元素多了
{
//我们要缩小滑动窗口，起码把当前这个多的元素踢出我们滑动窗口
len--;//滑动窗口减少了一个元素，大小也需要减少1
a[s[j] - 'a']--;
j++;
}
//printf("%dn",len);
}
return ans;
}
时间空间复杂度
第一次
优化
再优化
