題目

給定兩個字符串 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" 的異位詞。

提示:

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 僅包含小寫字母

代碼

完整代碼

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int* findAnagrams(char * s, char * p, int* returnSize) {int len_s = strlen(s);int len_p = strlen(p);int* result = (int*)malloc(len_s * sizeof(int));*returnSize = 0;if (len_s < len_p) {return result;}int hash_p[26] = {0};int hash_s[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;hash_s[s[i] - 'a']++;}for (int i = 0; i <= len_s - len_p; i++) {if (memcmp(hash_p, hash_s, 26 * sizeof(int)) == 0) {result[(*returnSize)++] = i;}if (i + len_p < len_s) {hash_s[s[i] - 'a']--;hash_s[s[i + len_p] - 'a']++;}}return result;
}

思路分析

1. 使用滑動窗口在字符串 s 上檢查長度為 len_p 的子串是否是 p 的異位詞。
2. 使用兩個哈希表分別記錄 p 和當前窗口內的字符頻率。
3. 滑動窗口每次移動時更新窗口內字符的頻率，并與 p 的頻率進行比較。

拆解分析

初始化哈希表

首先，我們需要記錄 p 中每個字符的頻率，同時記錄 s 中前 len_p 個字符的頻率。

int hash_p[26] = {0};
int hash_s[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;hash_s[s[i] - 'a']++;
}

滑動窗口檢查

通過比較兩個哈希表來判斷當前窗口是否是 p 的異位詞。如果是，則將當前窗口的起始索引加入結果。

for (int i = 0; i <= len_s - len_p; i++) {if (memcmp(hash_p, hash_s, 26 * sizeof(int)) == 0) {result[(*returnSize)++] = i;}if (i + len_p < len_s) {hash_s[s[i] - 'a']--;hash_s[s[i + len_p] - 'a']++;}
}

窗口移動

每次移動窗口時，更新窗口的字符頻率，然后繼續(xù)比較。

if (i + len_p < len_s) {hash_s[s[i] - 'a']--;hash_s[s[i + len_p] - 'a']++;
}

復雜度分析

• 時間復雜度：O(n)，其中 n 是字符串 s 的長度。初始化哈希表和滑動窗口移動都只需要遍歷 s 一次。
• 空間復雜度：O(1)，只需要兩個固定大小的哈希表來記錄字符頻率。

結果

一題多解

雙指針法

雙指針法思路分析

使用雙指針來維護一個滑動窗口，其中一個指針表示窗口的起始位置，另一個指針表示窗口的結束位置。通過計數(shù)器來記錄當前窗口內的字符頻率。

具體步驟：

1. 初始化兩個指針 left 和 right，以及一個計數(shù)器 count。
2. 移動 right 指針擴展窗口，并更新計數(shù)器。
3. 如果窗口大小等于 p 的長度，則檢查是否是異位詞。
4. 如果窗口大小超過 p 的長度，則移動 left 指針收縮窗口，并更新計數(shù)器。

雙指針法復雜度分析

• 時間復雜度：O(n)，每個字符最多被訪問兩次（一次通過 right 指針，一次通過 left 指針）。
• 空間復雜度：O(1)，只需要固定大小的哈希表和計數(shù)器。

完整代碼

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int* findAnagrams(char * s, char * p, int* returnSize) {int len_s = strlen(s);int len_p = strlen(p);int* result = (int*)malloc(len_s * sizeof(int));*returnSize = 0;if (len_s < len_p) {return result;}int hash_p[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;}int left = 0, right = 0, count = len_p;while (right < len_s) {if (hash_p[s[right++] - 'a']-- > 0) {count--;}if (count == 0) {result[(*returnSize)++] = left;}if (right - left == len_p && hash_p[s[left++] - 'a']++ >= 0) {count++;}}return result;
}

拆解分析

初始化哈希表

記錄 p 中每個字符的頻率。

int hash_p[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;
}

移動右指針

移動 right 指針擴展窗口，并更新計數(shù)器。

int left = 0, right = 0, count = len_p;while (right < len_s) {if (hash_p[s[right++] - 'a']-- > 0) {count--;}

檢查窗口

如果窗口大小等于 p 的長度，則檢查是否是異位詞。

if (count == 0) {result[(*returnSize)++] = left;
}

移動左指針

如果窗口大小超過 p 的長度，則移動 left 指針收縮窗口，并更新計數(shù)器。

if (right - left == len_p && hash_p[s[left++] - 'a']++ >= 0) {count++;
}

復雜度分析

• 時間復雜度：O(n)，每個字符最多被訪問兩次。
• 空間復雜度：O(1)，只需要固定大小的哈希表和計數(shù)器。

結果