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

一、题目（LeetCode 438 · 中等 · Hot100）

给定两个字符串 s 和 p（仅小写字母），找到 s 中所有 p 的异位词子串，返回这些子串的起始索引。异位词子串：长度等于 p、字母多重集与 p 完全相同的连续子串。

输入：s = "cbaebabacd", p = "abc"
输出：[0, 6]     // "cba" 与 "bac"

输入：s = "abab", p = "ab"
输出：[0, 1, 2]

二、思路演进

2.1 暴力：每个起点重算一次

对每个起点 i 截 s.substring(i, i+m) 排序后与排好序的 p 比较——O(n · m log m)；或每个起点数一遍 26 计数——O(n · (m + 26))。n、m 都是 3×10^4 量级时前者超时、后者贴边。

2.2 关键洞察：定长滑窗 + 增量计数

相邻窗口 [i-m+1, i] 与 [i-m+2, i+1] 只差进一个字符、出一个字符。计数数组不必重建，两个 O(1) 增量就能从上一个窗口滚到下一个。这正是滑窗的适用信号：窗口移动的代价远小于重算。变长滑窗的姊妹篇见 无重复字符的最长子串。

2.3 O(1) 判定：维护"不匹配种数"

统一维护差值计数 diff[c] = 窗口计数 - p 计数，再维护一个标量 mismatch = diff[c] != 0 的字符种数：

• 进字符 c：diff[c] 跨过 0 的边界时相应增减 mismatch；
• 出字符同理；
• mismatch == 0 即命中，判定 O(1)，连 26 个数的逐项比较都省掉了。

若不维护 mismatch，每个窗口 Arrays.equals 逐项比 26 个数也能过（每窗 O(26) 常数），但要能讲清两者代价差异。

三、复杂度分析

• 时间 O(n + m)：建 p 计数 O(m)、初始校验 26 格 O(26)，之后每个位置进出各一次 O(1)。对比暴力 O(n·(m+26))，省掉的是"每个窗口从头重算"的整块重复劳动。
• 空间 O(26)：两个计数数组与若干标量，与 n、m 无关。

四、代码

package org.example;

import java.util.ArrayList;
import java.util.List;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_438 {

    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc")); // 期望 [0, 6]
        System.out.println(findAnagrams("abab", "ab"));        // 期望 [0, 1, 2]
    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (m > n) {
            return ans;
        }

        int[] diff = new int[26];       // 窗口计数 - p 计数
        int mismatch = 0;               // 计数不等的字符种数
        for (int i = 0; i < m; i++) {
            diff[p.charAt(i) - 'a']--;  // 先记 p 的需求（负数 = 缺口）
        }
        for (int i = 0; i < 26; i++) {
            if (diff[i] != 0) {
                mismatch++;
            }
        }

        for (int i = 0; i < n; i++) {
            // s[i] 进窗口：判 0 变非 0 / 非 0 变 0，两个方向都要处理
            int in = s.charAt(i) - 'a';
            if (diff[in] == 0) mismatch++;
            diff[in]++;
            if (diff[in] == 0) mismatch--;

            if (i >= m) {
                // s[i-m] 出窗口，同样双向维护
                int out = s.charAt(i - m) - 'a';
                if (diff[out] == 0) mismatch++;
                diff[out]--;
                if (diff[out] == 0) mismatch--;
            }

            if (i >= m - 1 && mismatch == 0) {
                ans.add(i - m + 1);     // 窗口是 [i-m+1, i]
            }
        }
        return ans;
    }

}

五、坑点

• mismatch 的增减是双向的：进字符可能把某字符从"相等"变"不等"（mismatch++），也可能从"不等"变回"相等"（mismatch--）。只写一个方向是最常见的错法。
• 起点下标是 i - m + 1：窗口右端在 i，左端是 i-m+1，写成 i 会整体偏移。
• 先灌满再判定：i >= m - 1 之后窗口才满 m 格；用 i >= m 控制出窗、i >= m - 1 控制判定，两个条件差一，别混用。
• 出窗的字符是 s.charAt(i - m)：窗口满一格才出，第一轮不出窗。
• diff 用"窗口 − p"还是"p − 窗口"：方向要全程统一，混用导致 mismatch 判断失效。
• m > n 时直接返回空列表（本题数据保证 m ≤ n，工程上仍要防御）。

六、变形追问

• 变体一（最小覆盖子串，LeetCode 76，Hot100）：从"定长窗"换成"变长窗"。计数仍在，但判定从 mismatch == 0 变成"满足的种类数 = 需要的种类数"。且要收缩到不能再缩才记录答案，模板从 for 驱动变成 while 收缩驱动。
• 变体二（串联所有单词的子串，LeetCode 30）：匹配单位从字符变成单词，按单词长度做定长滑窗，多起点分组。考察"计数思想能否迁移到更大的匹配单位"。
• 变体三（字母异位词分组，LeetCode 49，Hot100）：同一计数思想在哈希分组里的应用——计数签名当 map key，互为异位词的串归同组。见 字母异位词分组。

2026-10 新增（E 轨 · Hot100 第一批）。