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

题目来源：438. 找到字符串中所有字母异位词 – 力扣（LeetCode）

---

📌 题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。 的子串，返回这些子串的起始索引。

• 异位词 指由相同字母重排列形成的字符串（包括相同的长度）。
• 不考虑答案输出的顺序。

---

✅ 示例解析

示例 1：

• 输入：s = "cbaebabacd", p = "abc"
• 输出：[0, 6]
• 解释：
  • 起始索引为 0 的子串是 "cba"，它是 "abc" 的异位词。
  • 起始索引为 6 的子串是 "bac"，它也是 "abc" 的异位词。

示例 2：

• 输入：s = "abab", p = "ab"
• 输出：[0, 1, 2]
• 解释：
  • "ab"（索引 0）、"ba"（索引 1）、"ab"（索引 2）均为 "ab" 的异位词。

示例 3：

• 输入：s = "a", p = "aa"
• 输出：[]
• 解释：s 长度小于 p，无法构成异位词。

---

⚠️ 提示

• 1 <= s.length, p.length <= 3 × 10⁴
• s 和 p 仅包含小写字母

---

💡 解法：滑动窗口 + 字符频次统计（数组模拟哈希表）—— O(n) 时间

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] scArr = s.toCharArray();
        char[] pcArr = p.toCharArray();

        if (scArr.length < pcArr.length) {
            return new ArrayList<>();
        }

        List<Integer> list = new ArrayList<>();
        int[] sCount = new int[26]; 
        int[] pCount = new int[26]; 

        for (int i = 0; i < pcArr.length; i++) {
            sCount[scArr[i] - 'a']++;
            pCount[pcArr[i] - 'a']++;
        }

        if (Arrays.equals(sCount, pCount)) {
            list.add(0);
        }

        for (int i = 0; i < scArr.length - pcArr.length; i++) {
            sCount[scArr[i] - 'a']--;
            sCount[scArr[i + pcArr.length] - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
                list.add(i + 1); 
            }
        }

        return list;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 遍历字符串 s 一次，每个字符最多被访问两次（初始化 + 滑动）。
  • Arrays.equals() 比较两个长度为 26 的数组，视为 O(1) 操作。
  • 总体时间复杂度为线性。
• 空间复杂度：O(1)
  • 使用两个固定长度为 26 的数组，空间不随输入规模增长。
  • 返回结果所用空间不计入额外空间复杂度。

---

🧩 解题思路

1. 核心思想：滑动窗口 + 字符频次匹配
   • 异位词的本质是：两个字符串中每个字符的出现次数完全相同。
   • 因此，我们只需在 s 上维护一个长度为 len(p) 的滑动窗口，判断其字符频次是否与 p 完全一致。
2. 初始化窗口：
   • 先统计 p 中所有字符的频次（pCount）。
   • 同时统计 s 的前 p.length() 个字符频次（sCount）。
   • 比较两个数组是否相等，若相等则索引 0 是一个答案。
3. 滑动窗口移动：
   • 每次将窗口右移一位：
     • 减去左边被移出字符的计数（sCount[left]--）
     • 加上右边新进入字符的计数（sCount[right]++）
   • 再次比较 sCount 和 pCount，若相等则记录当前窗口起始索引。
4. 为什么用数组而不用 HashMap？
   • 字符集仅为小写字母（26 个），使用 int[26] 更高效，避免哈希开销。
   • 数组索引直接通过 c - 'a' 计算，速度更快。
5. 边界处理：
   • 若 s.length < p.length，直接返回空列表。
   • 循环条件：i < s.length - p.length，确保不越界。