438. 找到字符串中所有字母异位词(滑动窗口，C解法）

题目描述：

给定两个字符串?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" 的异位词。

优秀解法：

int* findAnagrams(char * s, char * p, int* returnSize){
    int slen=strlen(s);
    int plen=strlen(p);
    *returnSize=0;
    if(slen<plen) return NULL;
    
    int len=slen-plen+1;
    int i,j;
    int *res=(int*)calloc(len,sizeof(int));
    int hash[26]={0};

    for(int i=0;i<plen;i++){
        hash[p[i]-'a']++;
        hash[s[i]-'a']--;
    }
    for(i=0;i<len;i++){
        for(j=0;j<26;j++) if(hash[j]) break;
        if(j>=26) res[(*returnSize)++]=i;
        hash[s[i]-'a']++;
        if(i+plen<slen) hash[s[i+plen]-'a']--;
    }
    return res;
}

来自用户：shugangwang

思路分析：

????????本题是一道固定窗口大小的滑动窗口问题。窗口的固定大小为 plen ，当前窗口的起始为 i ，当前窗口的结尾为 i+plen-1 。下一个窗口的起始为 i+1 ，即要淘汰的元素，下一个窗口的结尾为 i+plen，即要加入的元素。hash[i]表示对应字母需要的个数，字符串p中每含一个该字母，hash[i]加一，当前窗口里每加入一个该字母，hash[i]减一。更新新窗口时淘汰元素离开窗口，需要的该字母要加一，相应的加入元素进入窗口，需要的该字母要减一。用 j 遍历26个字母，若需要的字母都被满足了，则满足题意，加入题解数组。

边界分析：

????????在C中用数组和ASCII码实现hash表的映射，s[i]-'a'即为对应字母在hash表中的下标，因此只需要初始化大小为26的数组。要使滑动窗口的结尾不超过 s 字符串的大小，i 遍历最大到len，同时要注意遍历最后一个窗口时，没有下一个窗口了，用 if 语句限定窗口结尾防止遍历无定义地址报错。

易错细节：

1、len是字符串s与字符串p的差，需要先确定s>=p才能使用，否则会访问错误地址报错。同时，returnSize的初始化要在return NULL之前，否则从return NULL返回时returnSize还是空指针，会报错。

2、calloc是初始化为0的malloc，但是二者的参数传入不一样。malloc只需要一个参数，元素个数*元素大小，即分配的总空间，而calloc需要两个参数，分别传入元素个数和元素大小。calloc也可以用两条语句int *res = (int*)malloc(len * sizeof(int)); memset(res, 0, len * sizeof(int));代替。

相关题目链接（窗口大小不定的滑动窗口）：3.无重复字符的最长子串（滑动窗口，C解答）-CSDN博客