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

问题拆解

在字符串 s 里找出所有起始下标，使得从该下标开始、长度为 len(p) 的子串是 p 的字母异位词。异位词的判定标准很干脆：两边 26 个字母的出现次数完全相同，与顺序无关。

朴素做法是枚举每个起点，对长度为 m 的子串重新统计一遍字符计数再比较，时间是 O(n × m)。浪费在哪里？相邻两个窗口共享了 m - 1 个字符，却被从头数了两遍。窗口长度固定，右端进一个字符、左端出一个字符，其余全部不变——这正是定长滑动窗口的形状。

判定条件只依赖“计数是否相等”，而滑动一步只改动两个字符的计数，所以增量维护即可，不需要每步重算。

定长窗口 + 差异计数

进一步，连“每步比较两个长度 26 的数组”都可以省掉。只维护一个差值数组 cnt（窗口计数减去 p 的计数）和一个变量 diff（有多少个字母的差值非零），窗口是异位词当且仅当 diff == 0。每滑一步，进出各更新一次：某个字母的差值从 0 变成非 0，diff 加一；从非 0 变回 0，diff 减一。

public List<Integer> findAnagrams(String s, String p) {
    int n = s.length(), m = p.length();
    List<Integer> ans = new ArrayList<>();
    if (n < m) return ans;
    int[] cnt = new int[26]; // 窗口计数减 p 计数
    for (int i = 0; i < m; i++) {
        cnt[s.charAt(i) - 'a']++;
        cnt[p.charAt(i) - 'a']--;
    }
    int diff = 0; // 差值非零的字母个数
    for (int c : cnt) {
        if (c != 0) diff++;
    }
    if (diff == 0) ans.add(0);
    for (int i = m; i < n; i++) {
        int in = s.charAt(i) - 'a', out = s.charAt(i - m) - 'a';
        if (cnt[in] == 0) diff++;   // 原本平衡，进字符打破平衡
        cnt[in]++;
        if (cnt[in] == 0) diff--;   // 加完恰好归零
        if (cnt[out] == 0) diff++;  // 原本平衡，出字符打破平衡
        cnt[out]--;
        if (cnt[out] == 0) diff--;  // 减完恰好归零
        if (diff == 0) ans.add(i - m + 1);
    }
    return ans;
}

def findAnagrams(s: str, p: str) -> List[int]:
    n, m = len(s), len(p)
    if n < m:
        return []

    cnt = [0] * 26  # 窗口计数减 p 计数
    for i in range(m):
        cnt[ord(s[i]) - ord("a")] += 1
        cnt[ord(p[i]) - ord("a")] -= 1

    diff = sum(1 for c in cnt if c != 0)  # 差值非零的字母个数
    ans = [0] if diff == 0 else []

    for i in range(m, n):
        enter, leave = ord(s[i]) - ord("a"), ord(s[i - m]) - ord("a")
        if cnt[enter] == 0:
            diff += 1  # 原本平衡，进字符打破平衡
        cnt[enter] += 1
        if cnt[enter] == 0:
            diff -= 1  # 加完恰好归零
        if cnt[leave] == 0:
            diff += 1  # 原本平衡，出字符打破平衡
        cnt[leave] -= 1
        if cnt[leave] == 0:
            diff -= 1  # 减完恰好归零
        if diff == 0:
            ans.append(i - m + 1)

    return ans

func findAnagrams(s string, p string) []int {
    n, m := len(s), len(p)
    ans := []int{}
    if n < m {
        return ans
    }
    cnt := [26]int{} // 窗口计数减 p 计数
    for i := 0; i < m; i++ {
        cnt[s[i]-'a']++
        cnt[p[i]-'a']--
    }
    diff := 0 // 差值非零的字母个数
    for _, c := range cnt {
        if c != 0 {
            diff++
        }
    }
    if diff == 0 {
        ans = append(ans, 0)
    }
    for i := m; i < n; i++ {
        in, out := s[i]-'a', s[i-m]-'a'
        if cnt[in] == 0 {
            diff++ // 原本平衡，进字符打破平衡
        }
        cnt[in]++
        if cnt[in] == 0 {
            diff-- // 加完恰好归零
        }
        if cnt[out] == 0 {
            diff++ // 原本平衡，出字符打破平衡
        }
        cnt[out]--
        if cnt[out] == 0 {
            diff-- // 减完恰好归零
        }
        if diff == 0 {
            ans = append(ans, i-m+1)
        }
    }
    return ans
}

pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
    let (s, p) = (s.as_bytes(), p.as_bytes());
    let (n, m) = (s.len(), p.len());
    let mut ans = Vec::new();
    if n < m {
        return ans;
    }
    let mut cnt = [0i32; 26]; // 窗口计数减 p 计数
    for i in 0..m {
        cnt[(s[i] - b'a') as usize] += 1;
        cnt[(p[i] - b'a') as usize] -= 1;
    }
    let mut diff = cnt.iter().filter(|&&c| c != 0).count(); // 差值非零的字母个数
    if diff == 0 {
        ans.push(0);
    }
    for i in m..n {
        let enter = (s[i] - b'a') as usize;
        let leave = (s[i - m] - b'a') as usize;
        if cnt[enter] == 0 {
            diff += 1; // 原本平衡，进字符打破平衡
        }
        cnt[enter] += 1;
        if cnt[enter] == 0 {
            diff -= 1; // 加完恰好归零
        }
        if cnt[leave] == 0 {
            diff += 1; // 原本平衡，出字符打破平衡
        }
        cnt[leave] -= 1;
        if cnt[leave] == 0 {
            diff -= 1; // 减完恰好归零
        }
        if diff == 0 {
            ans.push((i - m + 1) as i32);
        }
    }
    ans
}

进出两个字符对 diff 的影响是对称的：进字符让 cnt[in] 加一，出字符让 cnt[out] 减一，但两者都遵循同一条规则——改动前差值为 0 说明这个字母原本平衡，改动会让 diff 加一；改动后差值恰好归零，说明这个字母重新平衡，diff 减一。最容易错的点是判断时机：加一的判断必须放在更新之前，减一的判断必须放在更新之后，四个 if 一个都不能挪位置。另外别忘了初始窗口本身也可能是答案，滑动之前要先检查一次 diff == 0。

复杂度

指标	复杂度	原因
时间	`O(n + m)`	建初始窗口 O(m)，之后每滑一步只做常数次计数更新
空间	`O(1)`	计数数组固定 26 个格子

可以迁移的模式

目标子串长度固定时优先想定长滑动窗口，每步只处理一进一出；
比较两个多重集合是否相等，可以压缩成“差值计数 + 非零项个数”，把整组比较降为 O(1)；
更新计数时用“改动前后是否跨越 0”来增量维护统计量，这个手法在带撤销的哈希计数里很常见。

567 题“字符串的排列”是同一份代码只把“收集所有下标”换成“找到一个就返回”，可以拿来当练手验证。