核心内容摘要
“中文字幕第一页”
个人主页Milestone-里程碑❄️个人专栏: 力扣hot100 CLinuxGitMySQL心向往之行必能至题目解读给定两个字符串s和p我们需要在s中找到所有是p的字母异位词的子串并返回这些子串的起始索引。
字母异位词指由相同字母重排列形成的字符串比如abc和cba就是一对异位词。
核心思路因为异位词的字符组成完全相同所以我们可以通过比较字符频率来判断两个字符串是否为异位词。
算法思路滑动窗口 字符计数这道题最优雅的解法就是滑动窗口它能让我们在O(n)的时间复杂度内解决问题具体步骤如下初始化字符计数数组先统计字符串p中每个字符的出现次数存入数组ch因为是小写字母数组大小设为 26 即可。
这个数组就像一个 “字符指纹”代表了p的字符组成。
滑动窗口遍历s用right指针作为窗口的右边界每次向右移动时就把当前字符在ch中的计数减 1。
如果某个字符的计数变成负数说明它在当前窗口中的出现次数超过了p中的次数此时需要移动左指针left并把移出窗口的字符计数加 1直到所有字符的计数都非负。
检查窗口是否有效当窗口的长度right - left 1恰好等于p的长度时说明当前窗口内的字符频率和p完全一致这就是一个异位词。
此时把左指针left加入结果列表即可。
完整代码实现cppclass Solution { public: vectorint findAnagrams(string s, string p) { vectorint 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]
{ ch[s[left] - a]; left; } // 窗口长度等于 p 的长度时记录起始索引 if (right - left 1 p.size()) { res.push_back(left); } } return res; } };代码解析字符计数数组ch[26]用来记录每个字符的出现次数通过字符 - a可以把字符映射到
的索引非常高效。
右指针扩张每次右指针移动就将对应字符的计数减 1代表该字符进入了当前窗口。
左指针收缩当某个字符的计数为负时说明它在窗口中出现过多需要移动左指针把移出窗口的字符计数加 1直到窗口内的字符计数都合法。
有效窗口判断当窗口长度等于p的长度时说明窗口内的字符频率和p完全一致此时左指针就是一个有效的起始索引。
复杂度分析时间复杂度O(n m)其中n是s的长度m是p的长度。
我们只需要遍历s和p各一次滑动窗口的每个元素最多被访问两次一次被右指针加入一次被左指针移出。
空间复杂度O(
因为我们只使用了一个大小为 26 的数组来记录字符计数空间开销是固定的。
总结这道题是滑动窗口算法的典型应用核心在于利用字符计数来维护窗口的有效性。
只要掌握了滑动窗口的 “扩张 - 收缩 - 验证” 思路这类子串匹配问题就能迎刃而解。