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

约 5 分钟
文章信息 10 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 10-20 LeetCode 热题 100 字节 华为 微软 百度
标签
字符串 哈希表 滑动窗口

题目描述

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

image-20260928220756622

题意分析

在字符串 s 中找出所有能通过重排得到 p 的连续子串，返回它们的起始下标。重排只改变字符顺序，不改变每个字符的数量，因此候选子串必须与 p 等长，且每种字母的出现次数都相同。

令 m = p.length()，只需检查 s 中所有长度为 m 的窗口。不同答案可以重叠；若 m 大于 s 的长度，则没有候选窗口。题目限定两个字符串非空且只含小写英文字母，可以用长度为 $26$ 的数组计数。

解法：固定长度滑动窗口

核心思路

[!blue]

若每移动一次窗口都重新统计其中的字符，会重复处理大量相同位置。相邻两个长度为 m 的窗口只差一个离开的左端字符和一个进入的右端字符，因此维护一份窗口频次即可。

need[c] 记录 p 中字母 c 的次数，建立后不再改变；window[c] 记录当前窗口中的次数。枚举右端点 right，先加入 s[right]。当 right >= m 时，移出 s[right-m]，使窗口重新只保留最近的 m 个字符。

完成更新后，窗口恰好覆盖 [max(0, right-m+1), right]。从 right == m-1 起，窗口才达到目标长度；此后只要两个频次数组逐项相等，就能通过重排得到 p，记录左端点 right-m+1。

每个长度为 m 的子串都有唯一的右端点，逐个枚举右端点就不会遗漏或重复检查任何候选。命中后仍只移动一位，重叠的匹配也会被保留。

解题步骤

  • 若 p 比 s 长，直接返回空列表。
  • 初始化 need 和 window，遍历 p 建立目标频次。
  • 从左到右枚举 right，先增加右端字符的频次，再在 right >= m 时减少下标 right - m 处字符的频次。
  • 当 right >= m - 1 时比较两个数组，相等便记录 right - m + 1；继续枚举直到 s 末尾。

第一次比较发生在 right == m-1，此时还没有字符需要移出；第一次移出发生在 right == m。这两个条件相差一位，分别控制“窗口已满”和“窗口超长”。

代码实现

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(\lvert p\rvert+26\lvert s\rvert)=O(\lvert p\rvert+\lvert s\rvert)$。先统计目标频次，每轮窗口更新为 $O(1)$，数组比较最多检查 $26$ 项。
  • 空间复杂度：$O(1)$，只使用两个长度为 $26$ 的数组。返回结果不计入额外空间，最多包含 $\max(0,\lvert s\rvert-\lvert p\rvert+1)$ 个下标。

关键点总结

[!green]

  • 异位词要求每种字符的数量完全一致，仅判断是否包含这些字符并不够。
  • 固定窗口长度后，每轮只修改进入和离开的两个字符频次，避免重复统计整个子串。
  • right-m 是移出的旧位置，right-m+1 是保留下来的新左端，也是答案下标。

易错点总结

[!yellow]

  • 未形成长度为 m 的窗口就开始判断，或允许窗口一直增长：候选长度必须与 p 一致。
  • 移出下标写成 right - m + 1：会删掉仍在窗口中的左端，正确下标是 right - m。
  • 到 right >= m 才开始比较：会漏掉第一个满窗口，正确条件是 right >= m - 1。
  • 起点写成 right - m：所有答案都会左移一位，正确公式是 right - m + 1。
  • Go 中把频次数组写成切片后直接比较：切片不可比较，应使用 [26]int 数组或逐项判断。
  • 找到一个匹配后跳过整个窗口：相邻答案可能重叠，右端点仍应每次只前进一位。

相似题目

题目 难度 关联与区别
567. 字符串的排列 中等 同样比较定长窗口的频次，本题记录全部匹配位置，原题只回答是否存在。
49. 字母异位词分组 中等 同样识别字母频次相同的字符串，原题按完整单词分组，本题滑动截取子串。
76. 最小覆盖子串 困难 用字符需求计数判断窗口是否覆盖目标；本题固定长度后记录所有异位词起点，该题收缩窗口寻找最短覆盖。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/59586946
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！