【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 个小写英文字母我们完全可以使用vectorint(26, 0)或者单纯的整型数组来代替哈希表。在 C 中vector也是重载了运算符的可以直接比较两个vector是否完全一致 C 代码实现 (数组哈希优化版)classSolution{public:vectorintfindAnagrams(string s,string p){vectorintres;intms.size(),np.size();// 长度不够直接返回空if(mn)returnres;// 使用长度为 26 的 vector 代替哈希表性能极高vectorintp_cnt(26,0);vectorintwin_cnt(26,0);// 1. 初始化目标字符串 p 的频次以及 s 中第一个窗口的频次for(inti0;in;i){p_cnt[p[i]-a];win_cnt[s[i]-a];}// 判断第一个窗口是否符合条件if(p_cntwin_cnt){res.push_back(0);}// 2. 窗口开始整体向右平移// i 指向即将移入窗口的右侧新字符for(intin;im;i){// 右边吃进一个新字符win_cnt[s[i]-a];// 左边吐出一个旧字符 (i - n 是滑出窗口的那个字符的索引)win_cnt[s[i-n]-a]--;// 直接比较两个 vector 是否完全一致if(p_cntwin_cnt){// i 是窗口右边界减去长度 n 再加 1就是窗口的起始索引res.push_back(i-n1);}}returnres;}};