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

2025-04-23 HGNULB 约 5 分钟

文章信息 10 个分类 3 个标签

分类

LeetCode CodeTop 中等已解决 10-20 字节跳动微软百度华为 LeetCode 热题 100

题目描述

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

题意分析

给定字符串 s 和 p，要求返回 s 中所有「与 p 互为字母异位词」的子串的起始下标。字母异位词的定义是：两个串包含完全相同的字母且每个字母出现次数相同，只是排列顺序可以不同。

把定义翻译成可执行的判据，就是「长度相同 + 26 个字母的出现次数逐一相同」。长度相同这一条极其关键：答案子串的长度恒等于 p 的长度，一个都不多、一个都不少。这意味着本题的窗口是定长的 —— 不需要去找什么最长、最短，也不需要根据条件伸缩边界，窗口尺寸从一开始就被题目钉死了。这一点是它和 3 题、76 题那类变长窗口的根本分野，写代码前先把它认下来，后面的判据和下标计算才不会飘。

约束信号：s 和 p 只含小写字母，长度上限 3 × 10^4。字符集固定为 26 让「计数」可以用定长数组而不是哈希表，比较两个窗口是否等价的代价被压成常数；长度上限则说明 $O(26n)$ 完全够用，不必为了抠到严格 $O(n)$ 而增加实现难度。

边界：p 比 s 长时不可能有答案，返回空列表；p 与 s 等长时最多只有一个候选，就是 s 自己；返回的下标是起点而不是终点，也不是子串本身。

解法：固定长度滑动窗口

核心思路

异位词要求长度相同且每个字符出现次数相同，因此答案只可能来自长度为 $m = p.length$ 的固定窗口。暴力为每个窗口重新计数需要 $O(nm)$；相邻窗口只变化一个入窗字符和一个出窗字符，可以用滑动窗口增量维护频次。

need 记录 p 的字符频次，window 记录当前窗口频次。每次先加入 s[right]；若窗口超过长度 $m$，再移除 s[right-m]。窗口装满后，两个长度为 $26$ 的数组相等就表示当前子串是异位词。

不变量是：处理完右端点 right 后，window 恰好记录区间 $[right-m+1,right]$（不足 $m$ 时记录已有前缀）的频次。因此匹配时的起点必为 right - m + 1，不会出现长度正确但计数来自其他区间的情况。

解题步骤

若 p 比 s 长，直接返回空列表。

统计 p 的 $26$ 个字母频次。

枚举右端点：加入当前字符；当 right >= m 时移除下标 right - m 的字符。

当 right >= m - 1 且两个频次数组相等时，记录起点 right - m + 1。

例如 s = "cbaebabacd"、p = "abc"，长度为 $3$ 的窗口依次滑动；cba 和 bac 的频次均为 a:1,b:1,c:1，对应起点为 [0,6]。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length()) {
            return res;
        }

        int[] need = new int[26];
        int[] window = new int[26];
        for (int i = 0; i < p.length(); i++) {
            need[p.charAt(i) - 'a']++;
        }

        for (int right = 0; right < s.length(); right++) {
            window[s.charAt(right) - 'a']++;
            if (right >= p.length()) {
                window[s.charAt(right - p.length()) - 'a']--;
            }
            if (right >= p.length() - 1 && Arrays.equals(need, window)) {
                res.add(right - p.length() + 1);
            }
        }
        return res;
    }
}

func findAnagrams(s string, p string) []int {
    res := make([]int, 0)
    if len(p) > len(s) {
        return res
    }

    need := [26]int{}
    window := [26]int{}
    for i := 0; i < len(p); i++ {
        need[p[i]-'a']++
    }

    for right := 0; right < len(s); right++ {
        window[s[right]-'a']++
        if right >= len(p) {
            window[s[right-len(p)]-'a']--
        }
        if right >= len(p)-1 && need == window {
            res = append(res, right-len(p)+1)
        }
    }
    return res
}

复杂度分析

时间复杂度：$O(26n) = O(n)$，每个窗口比较两个固定长度的频次数组。

空间复杂度：$O(1)$，只使用两个长度为 $26$ 的数组；返回结果不计入额外空间。

关键点总结

“异位词长度必须相同”决定窗口固定为 p.length()，无需变长窗口模板。

先加入右端，再在窗口超长时移出 right - m，可统一预热和滑动阶段。

字符集固定为小写字母，定长数组比哈希表更直接，比较成本也是常数。

若追问去掉频次数组的逐项比较，可维护不相等字符的数量；本题中 $26$ 是常数，当前实现更易写对。

易错点总结

套用变长窗口：s = "aab"、p = "ab" 时，包含 a、b 的 aab 长度不等，不能算异位词。

移出下标写成 right - m + 1：会删掉仍在窗口中的左端，正确下标是 right - m。

到 right >= m 才开始比较：会漏掉第一个满窗口，正确条件是 right >= m - 1。

起点写成 right - m：所有答案都会左移一位，正确公式是 right - m + 1。

Go 中把频次数组写成切片后直接比较：切片不可比较，应使用 [26]int 数组或逐项判断。

相似题目

题目	难度	考察点
3. 无重复字符的最长子串	中等	变长窗口求最长
30. 串联所有单词的子串	困难	定长窗口以单词为单位
49. 字母异位词分组	中等	用计数签名做哈希键
76. 最小覆盖子串	困难	变长窗口 + 缺口计数
242. 有效的字母异位词	简单	整串一次性计数比较
567. 字符串的排列	中等	定长窗口只判是否存在
LCR 014. 字符串的排列	中等	567 题的换皮版本
LCR 015. 找到字符串中所有字母异位词	中等	本题的换皮版本