滑动窗口-----找到所有字母异位词

🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

<<Git>><<MySQL>>

🌟心向往之行必能至

题目解读

给定两个字符串s和p，我们需要在s中找到所有是p的字母异位词的子串，并返回这些子串的起始索引。

• 字母异位词：指由相同字母重排列形成的字符串，比如"abc"和"cba"就是一对异位词。
• 核心思路：因为异位词的字符组成完全相同，所以我们可以通过比较字符频率来判断两个字符串是否为异位词。

算法思路：滑动窗口 + 字符计数

这道题最优雅的解法就是滑动窗口，它能让我们在O(n)的时间复杂度内解决问题，具体步骤如下：

1. 初始化字符计数数组

   • 先统计字符串p中每个字符的出现次数，存入数组ch（因为是小写字母，数组大小设为 26 即可）。
   • 这个数组就像一个 “字符指纹”，代表了p的字符组成。

2. 滑动窗口遍历s

   • 用right指针作为窗口的右边界，每次向右移动时，就把当前字符在ch中的计数减 1。
   • 如果某个字符的计数变成负数，说明它在当前窗口中的出现次数超过了p中的次数，此时需要移动左指针left，并把移出窗口的字符计数加 1，直到所有字符的计数都非负。

3. 检查窗口是否有效

   • 当窗口的长度（right - left + 1）恰好等于p的长度时，说明当前窗口内的字符频率和p完全一致，这就是一个异位词。
   • 此时把左指针left加入结果列表即可。

完整代码实现

cpp

class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> res; int ch[26] = {0}; // 统计 p 中每个字符的出现次数 for (int i = 0; i < p.size(); ++i) { ch[p[i] - 'a']++; } int left = 0; for (int right = 0; right < s.size(); ++right) { int c = s[right] - 'a'; ch[c]--; // 右指针字符进入窗口 // 如果当前字符计数为负，说明需要移动左指针 while (ch[c] < 0) { ch[s[left] - 'a']++; left++; } // 窗口长度等于 p 的长度时，记录起始索引 if (right - left + 1 == p.size()) { res.push_back(left); } } return res; } };

代码解析

• 字符计数数组：ch[26]用来记录每个字符的出现次数，通过字符 - 'a'可以把字符映射到 0-25 的索引，非常高效。
• 右指针扩张：每次右指针移动，就将对应字符的计数减 1，代表该字符进入了当前窗口。
• 左指针收缩：当某个字符的计数为负时，说明它在窗口中出现过多，需要移动左指针，把移出窗口的字符计数加 1，直到窗口内的字符计数都合法。
• 有效窗口判断：当窗口长度等于p的长度时，说明窗口内的字符频率和p完全一致，此时左指针就是一个有效的起始索引。

复杂度分析

• 时间复杂度：O(n + m)，其中n是s的长度，m是p的长度。我们只需要遍历s和p各一次，滑动窗口的每个元素最多被访问两次（一次被右指针加入，一次被左指针移出）。
• 空间复杂度：O(1)，因为我们只使用了一个大小为 26 的数组来记录字符计数，空间开销是固定的。

总结

这道题是滑动窗口算法的典型应用，核心在于利用字符计数来维护窗口的有效性。只要掌握了滑动窗口的 “扩张 - 收缩 - 验证” 思路，这类子串匹配问题就能迎刃而解。