【Hot 100 刷题计划】 LeetCode 438. 找到字符串中所有字母异位词 | C++ 滑动窗口题解
LeetCode 438. 找到字符串中所有字母异位词 | C++ 固定滑动窗口极致优化题解
📌 题目描述
题目级别：中等
给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词：指由相同字母重排列形成的字符串（包括相同的字符串）。换句话说，异位词就是字符种类相同，且每种字符出现次数也相同的字符串。
示例 1:
输入:s = "cbaebabacd", p = "abc"
输出:[0,6]
解释:
起始索引等于 0 的子串是"cba", 它是"abc"的异位词。
起始索引等于 6 的子串是"bac", 它是"abc"的异位词。
💡 解题思路：固定长度的滑动窗口
寻找连续的子串，必然用到滑动窗口。
由于异位词的一个重要前提是长度必须相等，所以我们不需要像通常的滑动窗口那样频繁地收缩和扩张，这道题的窗口大小是固定的，恒等于p.size()。
核心步骤：
- 频次统计：我们要判断两个字符串是否互为异位词，只需要判断它们包含的字符频次是否完全一致。
- 初始化窗口：先统计字符串
p的字符频次，并在字符串s中框出前p.size()个字符，统计这个初始窗口的字符频次。如果两者相等，就把索引0加入结果集。 - 整体平移：窗口开始向右滑动。每次滑动，实际上就是**“吃进”一个右边的新字符，同时“吐出”**一个左边的旧字符。
- 状态比对：每次滑动后，比对当前窗口的频次和
p的频次是否相同，如果相同，就记录当前窗口的起始索引。
🚀 性能优化杀手锏：数组代替哈希表
在判断频次时，普通哈希表（unordered_map）有较大的常数级时间开销。
由于题目限定了只包含26 个小写英文字母，我们完全可以使用vector<int>(26, 0)或者单纯的整型数组来代替哈希表。在 C++ 中，vector也是重载了==运算符的，可以直接比较两个vector是否完全一致！
💻 C++ 代码实现 (数组哈希优化版)
classSolution{public:vector<int>findAnagrams(string s,string p){vector<int>res;intm=s.size(),n=p.size();// 长度不够，直接返回空if(m<n)returnres;// 使用长度为 26 的 vector 代替哈希表，性能极高vector<int>p_cnt(26,0);vector<int>win_cnt(26,0);// 1. 初始化目标字符串 p 的频次，以及 s 中第一个窗口的频次for(inti=0;i<n;i++){p_cnt[p[i]-'a']++;win_cnt[s[i]-'a']++;}// 判断第一个窗口是否符合条件if(p_cnt==win_cnt){res.push_back(0);}// 2. 窗口开始整体向右平移// i 指向即将移入窗口的右侧新字符for(inti=n;i<m;i++){// 右边吃进一个新字符win_cnt[s[i]-'a']++;// 左边吐出一个旧字符 (i - n 是滑出窗口的那个字符的索引)win_cnt[s[i-n]-'a']--;// 直接比较两个 vector 是否完全一致if(p_cnt==win_cnt){// i 是窗口右边界，减去长度 n 再加 1，就是窗口的起始索引res.push_back(i-n+1);}}returnres;}};