438. 找到字符串中所有字母异位词【异位词-哈希数组】-Toy模板网

这篇具有很好参考价值的文章主要介绍了438. 找到字符串中所有字母异位词【异位词-哈希数组】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

438. 找到字符串中所有字母异位词

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

C代码1：异位词-哈希数组，此方法更加简单粗暴！更适用于考试！

// 滑动窗口的长度固定，
// 滑动窗口的字符串为异位词
// 异位词，直接锁定哈希数组、长度固定的滑动窗口右移，判断两个哈希数组相等不
// （方法不对，直接嗝屁，开始写之前一定要，确保方法是正确的！）
int* findAnagrams(char * s, char * p, int* returnSize){
    int lenS = strlen(s);
    int lenP = strlen(p);
    int arr[26] = {0};
    for (int i = 0; i < lenP; ++i) {
        arr[p[i] - 'a']++;
    }

    int ans[lenS];
    memset(ans, 0, sizeof(ans));
    int k = 0;
    for (int i = 0; i <= lenS - lenP; ++i) {  // 0123 01 i<2
        int arr1[26] = {0};
        for(int j = i; j < i + lenP; ++j) {
            arr1[s[j] - 'a']++;
        }
        if (equals(arr, arr1)) {
            ans[k++] = i;
        }
    }

    int* ans1 = (int*)malloc(sizeof(int) * k);
    for (int i = 0; i < k; ++i) {
        ans1[i] = ans[i];
    }
    *returnSize = k;
    return ans1;
}

C代码2：异位词-哈希数组：多了一些细节处理，优化内存文章来源地址https://www.toymoban.com/news/detail-426605.html

int* findAnagrams(char * s, char * p, int* returnSize){
    int lenS = strlen(s);
    int lenP = strlen(p); 
    if (lenS < lenP) {
        // int* arr = (int*)malloc(0);
        static int arr[0];
        *returnSize = 0;
        return arr;
    }
    int arr[26] = {0};   // 哈希数组到单一字母一定是26
    int arr1[26] = {0};
    
    int ans[lenS];
    memset(ans, 0, sizeof(ans));
    int k = 0;
    for (int i = 0; i < lenP; ++i) {  // 这里就要考虑是否越界了，测试样例肯定有！
        arr[p[i] - 'a']++;
        arr1[s[i] - 'a']++;
    }
    if (equals(arr, arr1)) {
        ans[k++] = 0;
    }

    for (int i = 0; i < lenS - lenP; ++i) {
        arr1[s[i] - 'a']--;
        arr1[s[i + lenP] - 'a']++;
        if (equals(arr, arr1)) {
            ans[k++] = i + 1;
        }
    }

    int* ans1 = (int*)malloc(sizeof(int) * k);
    for (int i = 0; i < k; ++i) {
        ans1[i] = ans[i];
    }
    *returnSize = k;
    return ans1;
}