LeetCode 438. 找到字符串中所有字母异位词 | 滑动窗口与字符计数数组解法

问题描述

给定两个字符串 s 和 p，要求找到 s 中所有是 p 的**字母异位词（Anagram）**的子串的起始索引。
字母异位词是指由相同字母重新排列形成的字符串（包含相同的字母且每个字母出现的次数相同）。
例如：

• 输入：s = "cbaebabacd", p = "abc"
  输出：[0, 6]
  解释：s 中从索引 0 开始的 "cba" 和索引 6 开始的 "bac" 均为 "abc" 的异位词。

核心思路：滑动窗口 + 字符计数数组

1. 字符计数数组

• 核心思想：通过固定长度的数组（长度26，对应26个小写字母）记录字符串中每个字符的出现次数。
• 比较机制：若两个字符串的字符计数数组相同，则它们是字母异位词。

2. 滑动窗口

• 窗口初始化：在 s 中初始化一个长度为 p.length() 的窗口。
• 窗口滑动：每次向右移动窗口，移除左边界字符的计数，增加右边界字符的计数。
• 实时比较：每次滑动后检查当前窗口的计数数组是否与 p 的计数数组一致。

算法步骤

1. 边界处理：若 s 的长度小于 p 或 p 为空，直接返回空列表。
2. 初始化计数数组：
   • pCount：统计 p 中每个字符的出现次数。
   • sCount：统计 s 中初始窗口（前 p.length() 个字符）的出现次数。
3. 初始窗口检查：若初始窗口的计数与 p 一致，记录索引 0。
4. 滑动窗口遍历：
   • 窗口每次右移一位，更新左边界字符的计数（减少）和右边界字符的计数（增加）。
   • 每次更新后检查计数数组是否匹配，若匹配则记录当前窗口的起始索引。

完整代码实现

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

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int m = p.length();
        int n = s.length();
        
        // 边界条件处理
        if (m == 0 || n < m) {
            return result;
        }

        int[] pCount = new int[26]; // 记录p的字符计数
        int[] sCount = new int[26]; // 记录当前窗口的字符计数

        // 初始化p和s的初始窗口的字符计数
        for (int i = 0; i < m; i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        // 检查初始窗口是否匹配
        if (Arrays.equals(pCount, sCount)) {
            result.add(0);
        }

        // 滑动窗口：每次移动一位，更新sCount并检查
        for (int i = 1; i <= n - m; i++) {
            // 移除左边界字符的计数
            int leftChar = s.charAt(i - 1);
            sCount[leftChar - 'a']--;

            // 添加右边界字符的计数
            int rightChar = s.charAt(i + m - 1);
            sCount[rightChar - 'a']++;

            // 检查当前窗口是否匹配
            if (Arrays.equals(pCount, sCount)) {
                result.add(i);
            }
        }

        return result;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
  滑动窗口遍历 s 需要 O(n)，每次窗口操作（更新计数和比较）的时间为常数。
• 空间复杂度：O(1)，使用固定长度的两个长度为26的数组。

关键点总结

1. 字符计数数组：利用数组索引映射字符，快速统计字符出现次数。
2. 滑动窗口优化：避免每次重新计算整个子串的计数，通过动态更新窗口边界字符的计数保证高效性。
3. 边界处理：注意字符串长度不足时的直接返回逻辑。

类似问题

• LeetCode 567. 字符串的排列：判断 s2 是否包含 s1 的排列。
• LeetCode 76. 最小覆盖子串：寻找覆盖目标字符的最短子串。