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

这道题真正在问什么

给字符串 s 和 p，找出 s 中所有「p 的字母异位词」子串的起始下标。异位词指字母种类和各自的个数都完全相同、只是排列顺序不同，比如 "cba" 是 "abc" 的异位词。题目里藏着一个决定解法形态的事实：异位词的长度必然等于 p 的长度——这直接把问题变成「检查 s 中每个长度为 len(p) 的窗口」。比如 s = "cbaebabacd"、p = "abc"，答案是 [0, 6]。

为什么想到定长滑动窗口

暴力做法是对每个起点截出长 k = len(p) 的子串，排序后和排序过的 p 比对，每个起点花 O(k log k)，整体 O(n · k log k)，重复劳动很多。

关键观察是：判断异位词根本不需要顺序信息，只需要「每个字母出现几次」这份统计；而相邻两个窗口只差两个字符——左端少一个、右端多一个，其余 k - 1 个字符原封不动。既然统计量只有两处变化，就没理由每次推倒重算，把计数表增量地改两格就够了。这正是定长滑动窗口的用武之地。

窗口计数怎么维护，何时判定命中

先统计 p 的字符计数 need，再统计 s 前 k 个字符组成的初始窗口计数 win，两表相等则下标 0 记入答案。之后窗口每右移一格：新进的字符 s[r] 计数加一，移出的字符 s[r - k] 计数减一（减到 0 就把该键删掉，保证两张表能直接判等），然后比较 win 与 need，相等就把起点 r - k + 1 记入答案。

全程保持的不变量是：win 永远精确等于当前窗口内各字符的出现次数。因此「win == need」当且仅当窗口是 p 的异位词，判定既不漏也不多。

为什么必须比次数而不是只比种类

p 里的字母可能重复，比如 p = "aab"：窗口 "abb" 字母种类和 p 一样是 {a, b}，但个数对不上，不是异位词。只用集合判断会放过这类假货，必须逐字母比较出现次数。

另一个方向的错误是让窗口变长变短——本题窗口大小恒等于 k，一旦写成「凑齐了就收缩」的变长窗口套路反而复杂化。定长窗口和变长窗口（如 LeetCode 76 最小覆盖子串）是滑动窗口的两个分支，本题因为「异位词长度确定」落在定长这一支，代码也因此更简单：右端每进一个，左端必出一个。

复杂度怎么算，边界在哪里

时间 O(n)：窗口右端把 s 扫一遍，每步做两次计数增减加一次计数比较；字母表固定 26 个小写字母，比较是 O(26) 的常数操作。空间 O(1)：两张计数表至多各存 26 个键，不随 n 增长。

最先要防的边界是 len(s) < len(p)：窗口根本摆不下，直接返回空数组，否则初始窗口的截取就会出错。另外结果记录的是起点 r - k + 1 而不是右端 r，下标换算写错一格，答案会整体偏移。

Python

from collections import Counter
def findAnagrams(s, p):
    k = len(p)
    if len(s) < k: return []
    need = Counter(p)
    win = Counter(s[:k])
    res = [0] if win == need else []
    for r in range(k, len(s)):
        win[s[r]] += 1            # 纳入新字符
        win[s[r - k]] -= 1        # 移出最左字符
        if win[s[r - k]] == 0:
            del win[s[r - k]]
        if win == need:
            res.append(r - k + 1)
    return res

C++

vector<int> findAnagrams(string s, string p){
    int k = p.size(), n = s.size();
    vector<int> res;
    if(n < k) return res;
    vector<int> need(26,0), win(26,0);
    for(char c : p) need[c-'a']++;
    for(int r = 0; r < n; r++){
        win[s[r]-'a']++;              // 纳入
        if(r >= k) win[s[r-k]-'a']--; // 移出最左
        if(r >= k-1 && win == need)
            res.push_back(r-k+1);
    }
    return res;
}

Java

public List<Integer> findAnagrams(String s, String p){
    List<Integer> res = new ArrayList<>();
    int k = p.length(), n = s.length();
    if (n < k) return res;
    int[] need = new int[26], win = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
    for (int r = 0; r < n; r++) {
        win[s.charAt(r) - 'a']++;              // 纳入
        if (r >= k) win[s.charAt(r - k) - 'a']--; // 移出最左
        if (r >= k - 1 && Arrays.equals(win, need))
            res.add(r - k + 1);
    }
    return res;
}