438. 找到字符串中所有字母异位词
题目描述
输入字符串 s 和 p。
如果 s 的某个子串与 p 长度相同，并且每种字母出现的次数都和 p 一样（即两者是字母异位词），就记下这个子串在 s 中的起始下标。
返回所有这样的起始下标，下标从 0 开始，顺序不限。没有符合条件的子串时返回空数组。
示例 1
输入：s = "cbaebabacd", p = "abc" 输出：[0,6]
解释：下标 0 处的 "cba" 和下标 6 处的 "bac" 都是 "abc" 的异位词。
示例 2
输入：s = "abab", p = "ab" 输出：[0,1,2]
解释：下标 0、1、2 开始的长度为 2 的子串分别是 "ab"、"ba"、"ab"，都符合。
数据范围
1 <= s.length, p.length <= 3 * 10^4s和p只含小写英文字母。
解题思路：滑动窗口 + 计数数组比较
维护长度为 len(p) 的固定窗口，用 26 个字符计数。右端加入字符，窗口超长时移除左端；计数相等时记录起点。
为什么正确
每次比较 win==need 前，win 表示当前窗口的字符频次，窗口长度为 min(i+1,k)；当 i>=k-1 时长度恰为 k，此前因总字符数不足不会命中。
复杂度分析
时间 O(|s|+|p|)（26 个小写英文字母）；辅助空间 O(26)=O(1)，不计输出；若有 m 个命中起点，含输出空间 O(26+m)。
易错点
窗口长度必须固定为 len(p)，先加入再移除旧字符时索引要对应 i-k。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findAnagrams(self, s,p):
if len(p)>len(s): return []
need=[0]*26; win=[0]*26; ans=[]; k=len(p)
for ch in p: need[ord(ch)-97]+=1
for i,ch in enumerate(s):
win[ord(ch)-97]+=1
if i>=k: win[ord(s[i-k])-97]-=1
if win==need: ans.append(i-k+1)
return ansclass Solution {
public List<Integer> findAnagrams(String s, String p) {
if (p.length() > s.length()) return new ArrayList<>();
int[] need = new int[26], win = new int[26]; List<Integer> ans = new ArrayList<>(); int k = p.length();
for (char ch : p.toCharArray()) need[ch - 'a']++;
for (int i = 0; i < s.length(); i++) {
win[s.charAt(i) - 'a']++;
if (i >= k) win[s.charAt(i - k) - 'a']--;
if (Arrays.equals(win, need)) ans.add(i - k + 1);
}
return ans;
}
}class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if (p.size() > s.size()) return {};
vector<int> need(26), win(26), ans; int k = p.size();
for (char ch : p) need[ch - 'a']++;
for (int i = 0; i < (int)s.size(); i++) {
win[s[i] - 'a']++;
if (i >= k) win[s[i - k] - 'a']--;
if (win == need) ans.push_back(i - k + 1);
}
return ans;
}
};func findAnagrams(s string, p string) []int {
if len(p) > len(s) {
return []int{}
}
var need, win [26]int; ans := []int{}; k := len(p)
for _, ch := range p {
need[ch-'a']++
}
for i, ch := range s {
win[ch-'a']++
if i >= k {
win[s[i-k]-'a']--
}
if win == need {
ans = append(ans, i-k+1)
}
}
return ans
}var findAnagrams = function(s, p) {
if (p.length > s.length) return [];
const need = new Array(26).fill(0), win = new Array(26).fill(0), ans = [], k = p.length;
for (const ch of p) need[ch.charCodeAt(0) - 97]++;
for (let i = 0; i < s.length; i++) {
win[s.charCodeAt(i) - 97]++;
if (i >= k) win[s.charCodeAt(i - k) - 97]--;
if (win.every((v, j) => v === need[j])) ans.push(i - k + 1);
}
return ans;
};function findAnagrams(s: string, p: string): number[] {
if (p.length > s.length) return [];
const need: number[] = new Array(26).fill(0), win: number[] = new Array(26).fill(0), ans: number[] = [], k = p.length;
for (const ch of p) need[ch.charCodeAt(0) - 97]++;
for (let i = 0; i < s.length; i++) {
win[s.charCodeAt(i) - 97]++;
if (i >= k) win[s.charCodeAt(i - k) - 97]--;
if (win.every((v, j) => v === need[j])) ans.push(i - k + 1);
}
return ans;
}其他解法
主解法每次比较两个计数数组，写法最简单；差异计数把比较的开销降为 O(1)，字符集很大时优势明显。
解法 2：优化的滑动窗口（差异计数） 时间 O(|s| + |p| + Σ)，空间 O(Σ)
count[c] 记录窗口中字母 c 的个数减去 p 中的个数，differ 记录 count 中非零的字母种数。窗口每移动一格只改两个字母，按“改之前为 0 则 differ 加 1，改之后为 0 则 differ 减 1”维护。differ 为 0 时窗口就是异位词。
每次移动 O(1)，不用每次比较整个 26 长度的数组。需要维护 differ，边界更容易写错。
class Solution:
def findAnagrams(self, s, p):
n, k = len(s), len(p)
if k > n:
return []
# count[c] = 窗口中 c 的个数 - p 中 c 的个数；differ = count 中非零的字母数
count = [0] * 26
for i in range(k):
count[ord(s[i]) - 97] += 1
count[ord(p[i]) - 97] -= 1
differ = sum(1 for c in count if c != 0)
ans = [0] if differ == 0 else []
def change(c, d):
nonlocal differ
if count[c] == 0:
differ += 1
count[c] += d
if count[c] == 0:
differ -= 1
for i in range(k, n):
change(ord(s[i - k]) - 97, -1)
change(ord(s[i]) - 97, 1)
if differ == 0:
ans.append(i - k + 1)
return ansclass Solution {
private int[] count;
private int differ;
private void change(int c, int d) {
if (count[c] == 0) differ++;
count[c] += d;
if (count[c] == 0) differ--;
}
public List<Integer> findAnagrams(String s, String p) {
int n = s.length(), k = p.length();
List<Integer> ans = new ArrayList<>();
if (k > n) return ans;
count = new int[26];
for (int i = 0; i < k; i++) {
count[s.charAt(i) - 'a']++;
count[p.charAt(i) - 'a']--;
}
differ = 0;
for (int c : count) if (c != 0) differ++;
if (differ == 0) ans.add(0);
for (int i = k; i < n; i++) {
change(s.charAt(i - k) - 'a', -1);
change(s.charAt(i) - 'a', 1);
if (differ == 0) ans.add(i - k + 1);
}
return ans;
}
}class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size(), k = p.size();
if (k > n) return {};
vector<int> count(26, 0);
for (int i = 0; i < k; i++) {
count[s[i] - 'a']++;
count[p[i] - 'a']--;
}
int differ = 0;
for (int c : count) if (c != 0) differ++;
vector<int> ans;
if (differ == 0) ans.push_back(0);
auto change = [&](int c, int d) {
if (count[c] == 0) differ++;
count[c] += d;
if (count[c] == 0) differ--;
};
for (int i = k; i < n; i++) {
change(s[i - k] - 'a', -1);
change(s[i] - 'a', 1);
if (differ == 0) ans.push_back(i - k + 1);
}
return ans;
}
};func findAnagrams(s string, p string) []int {
n, k := len(s), len(p)
ans := []int{}
if k > n {
return ans
}
count := [26]int{}
for i := 0; i < k; i++ {
count[s[i]-'a']++
count[p[i]-'a']--
}
differ := 0
for _, c := range count {
if c != 0 {
differ++
}
}
if differ == 0 {
ans = append(ans, 0)
}
change := func(c byte, d int) {
if count[c] == 0 {
differ++
}
count[c] += d
if count[c] == 0 {
differ--
}
}
for i := k; i < n; i++ {
change(s[i-k]-'a', -1)
change(s[i]-'a', 1)
if differ == 0 {
ans = append(ans, i-k+1)
}
}
return ans
}var findAnagrams = function(s, p) {
const n = s.length, k = p.length;
if (k > n) return [];
const count = new Array(26).fill(0);
for (let i = 0; i < k; i++) {
count[s.charCodeAt(i) - 97]++;
count[p.charCodeAt(i) - 97]--;
}
let differ = 0;
for (const c of count) if (c !== 0) differ++;
const ans = differ === 0 ? [0] : [];
const change = (c, d) => {
if (count[c] === 0) differ++;
count[c] += d;
if (count[c] === 0) differ--;
};
for (let i = k; i < n; i++) {
change(s.charCodeAt(i - k) - 97, -1);
change(s.charCodeAt(i) - 97, 1);
if (differ === 0) ans.push(i - k + 1);
}
return ans;
};function findAnagrams(s: string, p: string): number[] {
const n = s.length, k = p.length;
if (k > n) return [];
const count: number[] = new Array(26).fill(0);
for (let i = 0; i < k; i++) {
count[s.charCodeAt(i) - 97]++;
count[p.charCodeAt(i) - 97]--;
}
let differ = 0;
for (const c of count) if (c !== 0) differ++;
const ans: number[] = differ === 0 ? [0] : [];
const change = (c: number, d: number): void => {
if (count[c] === 0) differ++;
count[c] += d;
if (count[c] === 0) differ--;
};
for (let i = k; i < n; i++) {
change(s.charCodeAt(i - k) - 97, -1);
change(s.charCodeAt(i) - 97, 1);
if (differ === 0) ans.push(i - k + 1);
}
return ans;
}