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

◎

本节目标

用固定长度窗口维护 26 个小写字母频次，找出所有异位词起点。

这道题是滑动窗口解题框架的固定长度窗口母题。与模式串字符频次相同、长度也相同的连续片段，就是一个字母异位词。

查看原题

题意与约束

给定字符串 s 和 p，返回 s 中所有 p 的字母异位词子串起始下标，顺序按下标升序。如果 p 比 s 更长，答案为空。题目限定小写英文字母，因此可以用长度为 26 的数组表示频次。

为什么必须固定窗口长度

异位词要求字符种类和每个字符的数量都相同，窗口长度因此必须等于模式串长度。先统计 p 的频次；右端加入新字符后，如果窗口超过模式串长度，就把左端字符移出。长度恰好相等时，比较两个 26 维频次数组。

窗口从一个位置滑到下一个位置时，只有离开的左端字符和加入的右端字符发生变化。比起为每个起点重新统计模式串长度个字符，这把总扫描次数降为线性。

代码实现

C++ 使用固定大小数组，Python 使用长度为 26 的列表。二者都先处理右端，再在长度超过模式串时处理左端，因此每次比较前窗口长度不会超过模式串长度。

C++

C++17

#include <array>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        array<int, 26> need{};
        array<int, 26> window{};
        for (char ch : p) {
            need[ch - 'a']++;
        }

        vector<int> answer;
        int left = 0;
        for (int right = 0; right < static_cast<int>(s.size()); right++) {
            window[s[right] - 'a']++;
            if (right - left + 1 > static_cast<int>(p.size())) {
                window[s[left] - 'a']--;
                left++;
            }
            if (right - left + 1 == static_cast<int>(p.size()) && window == need) {
                answer.push_back(left);
            }
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        need = [0] * 26
        window = [0] * 26
        for ch in p:
            need[ord(ch) - ord("a")] += 1

        answer: list[int] = []
        left = 0
        for right, ch in enumerate(s):
            window[ord(ch) - ord("a")] += 1
            if right - left + 1 > len(p):
                window[ord(s[left]) - ord("a")] -= 1
                left += 1
            if right - left + 1 == len(p) and window == need:
                answer.append(left)
        return answer

复杂度分析

• 时间复杂度：O(n)，其中 n 是 s 的长度；每个窗口比较是固定 26 项。
• 空间复杂度：O(1)。两个频次数组大小固定。

易错点

• 只比较字符集合，不比较频次；aab 与 abb 的集合相同却不是异位词。
• 窗口长度超过模式串后忘记移出左端字符。
• 在 p 更长时访问不存在的完整窗口；自然保持长度条件即可返回空数组。

模式迁移

固定长度窗口也适合求长度为 k 的子数组最大和、统计满足某种频次条件的所有子串。若窗口中还要持续取得最大值或最小值，可进一步使用单调队列维护候选边界。