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

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

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

题意分析

给两个字符串 s 和 p，找出 s 中所有是 p 的字母异位词的子串，返回这些子串的起始下标（顺序不限）。字母异位词指由相同字母、相同数量重新排列而成的字符串。

「异位词」等价于「长度相同且各字符出现次数完全一致」，顺序信息完全无关。于是问题变成：在 s 中找出所有长度恰为 |p| 的窗口，使其字符频次向量与 p 的频次向量相等。

与「判断是否存在」的姊妹题相比，本题要求收集全部答案，因此命中后不能提前返回，必须一路滑到底。这也意味着答案的规模最大可达 $O(n)$，输出本身就是线性的。

窗口长度固定为 |p|，这是最强的实现信号：不需要收缩循环，窗口移动就是「右边进一个、左边出一个」的同步操作。字符集限定为小写字母，只有 26 种，频次向量可以用定长数组表示，比较是 $O(26)$ 的常数操作。数据规模 $ s , p \le 3 \times 10^4$，$O(26n)$ 完全够用。

边界有两处：|s| < |p| 时不可能有答案，必须先返回空列表，否则建初始窗口就会越界；另外起点为 $0$ 的窗口也是合法候选，建完初始窗口后要立刻检查一次，不能直接进入滑动循环。

解法：滑动窗口维护区间

核心思路

暴力做法是枚举 s 中每个长度为 n = |p| 的起点，把该子串重新统计频次（或排序）后与 p 比较，代价 $O(mn)$。瓶颈是：相邻两个窗口只差首尾两个字符，频次却被从头重算了一遍。

改造思路是增量维护：用一个长度 26 的数组 cnt1 记录当前窗口内各字符的出现次数，窗口右移一格时只做两次修改——新进入的字符计数加一，被挤出的字符计数减一。p 的频次 cnt2 建好后全程不变。

要维护的不变量是：在每次比较发生时，cnt1 恰好等于 s 中某个长度为 n 的窗口的字符频次。为了让这条不变量成立，两次计数更新必须都完成之后再比较——加入 s[i] 后窗口临时覆盖了 n + 1 个字符，只有移除 s[i - n] 之后才回到 n 个。

命中时要记录的是窗口的起始下标。当循环变量 i 指向刚加入的右端字符时，窗口覆盖 $[i - n + 1, i]$，所以答案是 i - n + 1。这是本题相对于「判存在」版本唯一多出来的推导，也是最容易写错一格的地方。

实现分两段：先用一趟循环同时填好 cnt2（p 的全部字符）和 cnt1（s 的前 n 个字符），比较一次并在相等时记下起点 $0$；然后从下标 n 开始逐格右移，每步「进一个、出一个、比一次」。

解题步骤

先判 m < n 直接返回空列表。这是防越界的前置条件，不是可选优化；返回空而不是 null，因为题目要求返回列表。

开两个长度 26 的定长计数数组。字符集已知且小，数组比哈希表常数小得多，还能整体比较。

一趟循环同时填 cnt1 的前 n 位与 cnt2 的全部。两者长度都是 n，合并成一次扫描最省事。

建完初始窗口立刻比较，相等就记下起点 $0$。漏掉这一步，s = "abc"、p = "cba" 这种答案就在开头的用例会被整个丢掉。

从 i = n 开始右移：先 ++cnt1[s[i]]（右端进），再 --cnt1[s[i - n]]（左端出）。i - n 正是刚被挤出窗口的那个下标。

两次更新之后才比较，相等时把 i - n + 1 加入答案。起点是「右端下标减窗口长度再加一」，可以用「窗口覆盖 $[i-n+1, i]$，共 n 个字符」来自检。

命中后不返回，继续滑动，因为要收集全部答案。

循环结束返回答案列表。

以 s = "cbaebabacd"、p = "abc" 走一遍，期望答案 [0, 6]。m = 10、n = 3。建表：cnt2 为 {a:1, b:1, c:1}；cnt1 取 s 的前三位 "cba"，同样是 {a:1, b:1, c:1}。首次比较相等，记下起点 0。i = 3：加入 'e'、移除 s[0] = 'c'，窗口为 "bae"，频次 {a:1, b:1, e:1}，不等。i = 4：加入 'b'、移除 s[1] = 'b'，窗口为 "aeb"，频次不变，仍不等。i = 5：加入 'a'、移除 s[2] = 'a'，窗口为 "eba"，仍不等。i = 6：加入 'b'、移除 s[3] = 'e'，窗口为 "bab"，频次 {a:1, b:2}，不等。i = 7：加入 'a'、移除 s[4] = 'b'，窗口为 "aba"，频次 {a:2, b:1}，不等。i = 8：加入 'c'、移除 s[5] = 'a'，窗口为 "bac"，频次 {a:1, b:1, c:1}，相等，记下起点 8 - 3 + 1 = 6。i = 9：加入 'd'、移除 s[6] = 'b'，窗口为 "acd"，不等。返回 [0, 6]。可以看到 i = 4 和 i = 5 两轮里进出的是同一个字符，频次数组毫无变化——增量维护自动跳过了这类无效重算。

代码实现

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<Integer> answer = new ArrayList<>();
        // 长度不够时无解，同时防止建初始窗口越界。
        if (m < n) {
            return answer;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
            ++cnt1[s.charAt(i) - 'a'];
            ++cnt2[p.charAt(i) - 'a'];
        }
        // 起点为 0 的窗口也是候选。
        if (Arrays.equals(cnt1, cnt2)) {
            answer.add(0);
        }
        for (int i = n; i < m; ++i) {
            // 右端进、左端出，两次更新后窗口长度回到 n。
            ++cnt1[s.charAt(i) - 'a'];
            --cnt1[s.charAt(i - n) - 'a'];
            if (Arrays.equals(cnt1, cnt2)) {
                // 窗口覆盖 [i - n + 1, i]，起点是 i - n + 1。
                answer.add(i - n + 1);
            }
        }
        return answer;
    }
}

func findAnagrams(s string, p string) (answer []int) {
    m, n := len(s), len(p)
    if m < n {
        return
    }
    // 定长数组是值类型，可直接用 == 整体比较。
    var cnt1, cnt2 [26]int
    for i, ch := range p {
        cnt1[s[i]-'a']++
        cnt2[ch-'a']++
    }
    if cnt1 == cnt2 {
        answer = append(answer, 0)
    }
    for i := n; i < m; i++ {
        cnt1[s[i]-'a']++
        cnt1[s[i-n]-'a']--
        if cnt1 == cnt2 {
            answer = append(answer, i-n+1)
        }
    }
    return
}

复杂度分析

时间复杂度：$O(26m + n)$，即 $O(m + n)$。窗口右移 $m - n$ 次，每次两次常数级计数更新加一次长度 26 的比较；建表是 $O(n)$。凭的是增量更新——相邻窗口只差首尾两个字符，绝不重新统计整段。

空间复杂度：$O(1)$（不计返回值）。两个长度 26 的定长数组与输入规模无关；答案列表是题目要求的输出，不计入额外空间。

关键点总结

「异位词 / 排列」一律转成「长度相同 + 频次向量相等」，把顺序信息直接丢掉，是这一族题的统一入口。

窗口长度固定时不需要收缩循环，只有同步的一进一出；识别出「定长」能省掉一整层 while，也消除了「答案在收缩前还是收缩后更新」这个常见坑。

起点下标 i - n + 1 要靠「窗口覆盖 $[i-n+1, i]$」来推，而不是靠记忆。写完立刻用一个长度为 $1$ 的窗口自检：n = 1 时起点应等于 i，公式代入正好成立。

「求存在性」与「求全部解」的差别只在于命中后是 return 还是 add 后继续；识别这一点能让一份模板同时覆盖两道题。

字符集有限时用定长计数数组：常数小、可整体比较；Go 的定长数组是值类型可直接 ==，Java 的数组必须用 Arrays.equals。

面试视角：这题面试官期待的就是 $O(n)$ 的定长窗口。写完后主动指出「每次比较是 $O(26)$，可以再引入一个 diff 变量记录『还有多少种字符频次不匹配』，把比较降到 $O(1)$」是加分项；被追问「和 567 题有什么区别」，答「只是命中后不提前返回」，说明你看到了模板的可复用性。

易错点总结

错误写法：漏掉 m < n 的前置判断。输入 s = "ab"、p = "abc" 时建初始窗口就会访问 s.charAt(2)，直接下标越界。

错误写法：建完初始窗口不比较就进入滑动循环。输入 s = "abc"、p = "cba" 会返回空列表，而正确答案是 [0]。

错误写法：命中时加入 i 而不是 i - n + 1。输入 s = "cbaebabacd"、p = "abc" 会返回 [2, 8]，全部偏移了 n - 1 格。

错误写法：命中时加入 i - n。少了一格，同一用例会返回 [-1, 5]，第一个甚至是负数。

错误写法：移出的下标写成 i - n + 1。窗口左端多留一个字符，输入 s = "cbaebabacd"、p = "abc" 会返回 [0, 3, 4, 5] 而不是 [0, 6]。

错误写法：先比较再更新计数。比较用的是上一轮的窗口状态，整体延迟一格，输入 s = "abcab"、p = "ab" 会返回 [0, 1] 而不是 [0, 3]。

错误写法：命中后 return。这是把 567 题的写法照搬过来，输入 s = "cbaebabacd"、p = "abc" 只会返回 [0]，漏掉 6。

错误写法：Java 里用 cnt1 == cnt2 比较两个 int[]。比的是引用，恒为 false，任何输入都返回空列表。

错误写法：每个窗口用 s.substring(i, i + n) 取子串再排序比较。逻辑对但每步 $O(n \log n)$ 且不断创建新字符串，$3 \times 10^4$ 的规模会超时。

错误写法：只比较字符种类集合而不比较次数。输入 s = "abb"、p = "aab" 会误判命中并返回 [0]，正确答案是空列表。

相似题目

题目	难度	考察点
438. 找到字符串中所有字母异位词	中等	与本题同题，可直接套用同一份定长窗口
567. 字符串的排列	中等	只问存在性，命中即可提前返回，无需推导起点下标
LCR 014. 字符串的排列	中等	与 567 同题，是「返回布尔」与「收集下标」这一差别的直接对照
76. 最小覆盖子串	困难	窗口长度可变，条件从「精确相等」放宽为「覆盖」，需在收缩中求最短
3. 无重复字符的最长子串	中等	同为字符窗口但求最长，收缩条件是窗口内出现重复字符
30. 串联所有单词的子串	困难	把「字符」换成「等长单词」，需按单词长度分组跑多条并行窗口