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

中等通过率 54.6%python3核心代码模式滑动窗口样例通过牛客 AC哈希表字符串滑动窗口

一句话

定长滑动窗口，用 26 位计数表加一个 diff 标量比对。

解题思路¶

这题考什么¶

要在 s 里找出所有「与 p 恰好是字母异位词」的子串的起始下标。异位词（anagram，字母重排得到的另一个词）与顺序无关，只取决于字母多重集合，所以子串必然与 p 等长——这把问题限定成了定长窗口：窗口宽度固定为 len(p)，从左滑到右，每个位置判一次「窗口的字母计数是否等于 p 的」。

朴素做法是每个位置都排序或重新数一遍，O(n * m log m)。定长窗口的好处是相邻两个窗口只差两个字符（右边进一个、左边出一个），计数表可以增量更新，每步 O(1)。见双指针与滑动窗口。

剩下的问题是「两张 26 位计数表是否相等」这个判断本身。逐位比要 26 次，虽然是常数但每步都做就是 26n 次。本题解用一个标量 diff 把它压成 O(1)：

diff = 当前有多少个字母的计数还对不上（窗口计数 != p 的计数）
每次某个字母的计数发生 +1 或 -1，只需看**这一个字母**在改动前后
是否「对得上」，据此把 diff 加一或减一
diff == 0  <=>  两张表完全相同  <=>  窗口是 p 的异位词

也就是把 26 维的相等判断维护成一个增量标量。写法上更常见的是直接 if window == need（Python 比两个长度 26 的 list 也很快），这里选 diff 是为了让「每步严格 O(1)」这件事显式。

数据规模与复杂度¶

1 <= len(s), len(p) <= 3e4，两者都只含小写字母。时间 O(n)：窗口右端扫一遍 s，每步做常数次计数更新与 diff 调整；空间 O(1)：两张长度固定为 26 的计数表，与输入规模无关。「每个起点重排一次」是 O(n * m log m)，最坏 3e4 * 3e4 * 15，完全不可行。

坑在哪¶

len(p) > len(s) 时必须提前返回空列表。不然窗口根本凑不满，后面基于「窗口已满」的下标计算会算出负数起点。
下标偏移：右端为 right 的窗口，其左端是 right - m + 1（m = len(p)），窗口长度是闭区间的 right - left + 1。少写这个 +1，起点会整体差一格，示例 1 的答案会变成 [-1, 5] 之类的错值。
字母到下标的映射用 ord(c) - ord("a")，减的是小写 a 的码位。题面保证只有小写字母，所以下标必落在 0..25；若拿大写字母的码位去减，索引会变成负数，Python 不报错而是从数组尾部取值，错得很隐蔽。
diff 的维护顺序不能颠倒：先看改动前这一位是否相等，再改计数，再看改动后是否相等。把「改计数」提到最前面，比较的就是同一个新值， diff 永远调不动。
左端移出的动作只在窗口已经满员之后才做（right >= m），否则会把根本没进过窗口的字符计数减成负数。
严格比对：题面虽写「不考虑答案输出的顺序」，但本解法按 right 从小到大扫，产出的起点天然升序，与判题期望的顺序一致，所以走的是严格比对，不需要 unordered 放宽。

样例复核¶

s = "cbaebabacd"，p = "abc"，m = 3，need = a:1 b:1 c:1，期望 [0, 6]。

right=0 'c' 入窗       窗口 "c"    未满
right=1 'b' 入窗       窗口 "cb"   未满
right=2 'a' 入窗       窗口 "cba"  满且 diff=0 -> 记下起点 2-3+1 = 0
right=3 'e' 入，'c' 出 窗口 "bae"  diff!=0
right=4 'b' 入，'b' 出 窗口 "aeb"  diff!=0（少 c 多 e）
right=5 'a' 入，'a' 出 窗口 "eba"  diff!=0
right=6 'b' 入，'e' 出 窗口 "bab"  diff!=0（多一个 b，缺 c）
right=7 'a' 入，'b' 出 窗口 "aba"  diff!=0
right=8 'c' 入，'b' 出 窗口 "bac"  diff=0 -> 记下起点 8-3+1 = 6
right=9 'd' 入，'a' 出 窗口 "acd"  diff!=0

得到 [0, 6]，与样例一致。

参考实现¶

solutions/leetcode/LC438/sol.py
from typing import List, Optional


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n = len(s)
        m = len(p)
        # 异位词与 p 等长，所以 s 比 p 还短时不可能有答案；
        # 不提前返回的话，后面按 right - m + 1 算起点会得到负数下标
        if m > n:
            return []
        # 两张长度 26 的计数表：need 是 p 的字母分布，window 是当前窗口的分布。
        # 只含小写字母，故用 ord(c) - ord("a") 把字母映射到 0..25
        need = [0] * 26
        window = [0] * 26
        for ch in p:
            need[ord(ch) - ord("a")] += 1
        # diff = 当前有多少个字母的计数对不上。它把「两张 26 位表是否相等」
        # 压成一个标量：diff == 0 当且仅当两表完全相同。
        # 初始窗口为空，凡是 p 里用到的字母都对不上，先数出来
        diff = sum(1 for c in need if c != 0)
        ans = []
        for right in range(n):
            # 右端进一个字符：只有这一位的计数会变，所以只需重估这一位对 diff 的贡献。
            # 顺序必须是「先看改前是否相等 -> 改计数 -> 再看改后是否相等」，
            # 把改计数提到最前面，两次比较的就是同一个新值，diff 永远调不动
            i = ord(s[right]) - ord("a")
            if window[i] == need[i]:
                diff += 1               # 本来对得上，加了之后必然对不上
            window[i] += 1
            if window[i] == need[i]:
                diff -= 1               # 加完正好补齐这一位
            # 窗口宽度固定为 m，右端到了 m 之后每进一个就要出一个，
            # 出的是下标 right - m 那个字符（新窗口的左端是 right - m + 1）
            if right >= m:
                j = ord(s[right - m]) - ord("a")
                if window[j] == need[j]:
                    diff += 1
                window[j] -= 1
                if window[j] == need[j]:
                    diff -= 1
            # 窗口满员（right + 1 >= m）且两张表一致时，记下起点。
            # 闭区间左端 = right - m + 1，少写这个 +1 起点会整体差一格
            if right >= m - 1 and diff == 0:
                ans.append(right - m + 1)
        return ans

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