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

理解题目：

题目要求在给定的字符串 s 中，找出所有是字符串 p 的字母异位词的子串，并返回这些子串的起始索引。

代码实现：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindAllAnagramsInString {
    // 找出字符串中所有字母异位词的起始索引
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>(); // 存储结果的列表
        if (s == null || s.length() == 0 || p == null || p.length() == 0 || s.length() < p.length()) {
            return result; // 边界条件处理
        }

        // 统计目标字符串 p 中字符的频率
        Map<Character, Integer> pFreq = new HashMap<>();
        for (char c : p.toCharArray()) {
            pFreq.put(c, pFreq.getOrDefault(c, 0) + 1);
        }

        // 使用滑动窗口在字符串 s 上进行遍历
        Map<Character, Integer> windowFreq = new HashMap<>(); // 存储当前窗口内字符的频率
        int left = 0, right = 0, match = 0; // 左右指针和匹配字符数量

        while (right < s.length()) {
            char rightChar = s.charAt(right);
            if (pFreq.containsKey(rightChar)) {
                windowFreq.put(rightChar, windowFreq.getOrDefault(rightChar, 0) + 1);
                if (windowFreq.get(rightChar).equals(pFreq.get(rightChar))) {
                    match++;
                }
            }
            right++;

            // 如果滑动窗口包含了 p 的所有字符，则找到一个字母异位词，将起始索引添加到结果中
            while (match == pFreq.size()) {
                if (right - left == p.length()) {
                    result.add(left);
                }

                char leftChar = s.charAt(left);
                if (pFreq.containsKey(leftChar)) {
                    windowFreq.put(leftChar, windowFreq.get(leftChar) - 1);
                    if (windowFreq.get(leftChar) < pFreq.get(leftChar)) {
                        match--;
                    }
                }
                left++;
            }
        }

        return result;
    }
}

步骤解释：

1. 创建一个结果列表 result 用于存储找到的字母异位词的起始索引。

2. 首先对边界条件进行处理，如果字符串 s 为空，字符串 p 为空，或者字符串 s 的长度小于字符串 p 的长度，则直接返回空结果列表。

3. 统计字符串 p 中每个字符的出现次数，使用哈希表 pFreq 存储字符频率。

4. 使用滑动窗口在字符串 s 上进行遍历，初始化左右指针 left 和 right，以及匹配字符数量 match。

5. 遍历字符串 s，将字符加入窗口并更新窗口中字符的频率。

6. 如果窗口中的字符频率与字符串 p 中的字符频率相匹配，则增加匹配字符数量 match。

7. 如果 match 等于字符串 p 中字符数量，则说明找到一个字母异位词，将起始索引添加到结果列表中。

8. 左指针向右移动，缩小窗口，继续遍历直到遍历完整个字符串 s。