【子串-1】438.找到字符串中所有字母异位词

题目描述给定两个字符串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]解释:起始索引等于 0 的子串是 ab, 它是 ab 的异位词。 起始索引等于 1 的子串是 ba, 它是 ab 的异位词。 起始索引等于 2 的子串是 ab, 它是 ab 的异位词。解题思路方法一滑动窗口哈希表我的方法是用滑动窗口哈希表处理用valid变量记录已经匹配的字符种类数当valid need.size()时说明窗口内的字符计数和p完全一致。关键变量变量含义needp中每个字符需要的数量window当前窗口中每个字符的数量valid已经完全匹配的字符种类数什么是完全匹配对于某个字符c如果window[c] need[c]说明字符c的数量已经匹配valid如果window[c] ! need[c]说明还没匹配不计入valid当valid need.size()时说明所有字符都匹配了当前窗口就是一个字母异位词。具体过程示例s cbaebabacd, p abc初始化need {a:1, b:1, c:1} (size 3) window {} valid 0滑动过程is[i]操作windowvalid判断0c加入 c{c:1}0-1b加入 b{c:1, b:1}0-2a加入 a{c:1, b:1, a:1}3valid3 ✅ → 记录 03e加入 e移除 c{b:1, a:1, e:1}2-4b加入 b移除 b{a:1, e:1, b:1}2-5a加入 a移除 a{e:1, b:1, a:1}2-6b加入 b移除 e{b:2, a:1}1-7a加入 a移除 b{b:1, a:2}1-8c加入 c移除 a{b:1, a:1, c:1}3valid3 ✅ → 记录 69d加入 d移除 b{a:1, c:1, d:1}1-结果[0, 6]✅代码实现class Solution { public: vectorint findAnagrams(string s, string p) { vectorint result; int n s.size(), m p.size(); if (n m) return result; unordered_mapchar, int need, window; for (char c : p) need[c]; // 统计 p 的字符需求 int valid 0; // 已匹配的字符种类数 for (int i 0; i n; i) { // 右边加入新字符 char c s[i]; if (need.count(c)) { // 如果这个字符在 p 中 window[c]; // 窗口计数 1 if (window[c] need[c]) // 如果数量刚好匹配 valid; // 匹配种类 1 } // 左边移除旧字符 if (i m) { // 窗口大小超过 m需要移除左边 char d s[i - m]; if (need.count(d)) { // 如果这个字符在 p 中 if (window[d] need[d]) // 如果移除前是匹配的 valid--; // 匹配种类 -1 window[d]--; // 窗口计数 -1 } } // 判断当前窗口 if (valid need.size()) { // 所有字符都匹配 result.push_back(i - m 1); // 记录起始索引 } } return result; } };复杂度分析维度复杂度说明时间复杂度O(n m)遍历s一次遍历p一次空间复杂度O(k)k是字符集大小小写字母时 O(1)看了题解后发现了其他方法。方法二滑动窗口 字符计数为什么用滑动窗口因为我们要找的是固定长度的子串窗口大小固定为p.length()。窗口从左往右滑动每次移动一位左边移除一个字符右边加入一个字符判断窗口内的字符计数是否和p相同如何快速判断两个计数是否相同用两个数组或哈希表need[26]p中每个字符的出现次数window[26]当前窗口中每个字符的出现次数每次滑动后比较need和window是否完全相同。代码实现class Solution { public: vectorint findAnagrams(string s, string p) { vectorint result; int n s.size(), m p.size(); if (n m) return result; vectorint need(26, 0); // p 的字符计数 vectorint window(26, 0); // 当前窗口的字符计数 // 统计 p 的字符计数 for (char c : p) { need[c - a]; } // 初始化第一个窗口 for (int i 0; i m; i) { window[s[i] - a]; } // 判断第一个窗口 if (need window) result.push_back(0); // 滑动窗口 for (int i m; i n; i) { // 右边加入新字符 window[s[i] - a]; // 左边移除旧字符 window[s[i - m] - a]--; // 判断当前窗口 if (need window) { result.push_back(i - m 1); } } return result; } };具体过程示例s cbaebabacd, p abcneed [1,1,1,0,0,...,0] (a:1, b:1, c:1) 初始窗口: cba (i0~2) window [1,1,1,0,...] need ✅ → result [0] i3: 加入 e移除 c 窗口: bae window [1,1,0,0,1,...] ! need ❌ i4: 加入 b移除 b 窗口: aeb window [1,1,0,0,1,...] ! need ❌ i5: 加入 a移除 a 窗口: eba window [1,1,0,0,1,...] ! need ❌ i6: 加入 b移除 e 窗口: bab window [1,2,0,...] ! need ❌ i7: 加入 a移除 b 窗口: aba window [2,1,0,...] ! need ❌ i8: 加入 c移除 a 窗口: bac window [1,1,1,0,...] need ✅ → result [0, 6] i9: 加入 d移除 b 窗口: acd window [1,0,1,1,...] ! need ❌ 结果: [0, 6] ✅复杂度分析维度复杂度说明时间复杂度O(n m)初始化 O(m)滑动 O(n)每次比较 O(26) O(1)空间复杂度O(1)两个固定大小 26 的数组方法三滑动窗口 差异计数优化版核心优化上面的解法每次滑动后都要比较整个need和window数组O(26)。我们可以用一个变量diff记录有多少个字符的计数不匹配当diff 0时说明完全匹配。代码实现class Solution { public: vectorint findAnagrams(string s, string p) { vectorint result; int n s.size(), m p.size(); if (n m) return result; vectorint count(26, 0); // 差异数组 int diff 0; // 不匹配的字符种类数 // 统计 p 的计数正数和 s 前 m 个字符的计数负数 for (int i 0; i m; i) { count[p[i] - a]; count[s[i] - a]--; } // 统计 diff for (int i 0; i 26; i) { if (count[i] ! 0) diff; } if (diff 0) result.push_back(0); // 滑动窗口 for (int i m; i n; i) { // 加入右边字符 int right s[i] - a; if (count[right] 0) diff; // 从匹配变不匹配 count[right]--; if (count[right] 0) diff--; // 从不匹配变匹配 // 移除左边字符 int left s[i - m] - a; if (count[left] 0) diff; count[left]; if (count[left] 0) diff--; if (diff 0) { result.push_back(i - m 1); } } return result; } };复杂度分析维度复杂度说明时间复杂度O(n m)每次滑动 O(1)空间复杂度O(1)固定大小 26 的数组比方法二更快因为每次滑动只做常数次操作不需要比较整个数组。三种方法的复杂度总结方法时间复杂度空间复杂度适用场景数组计数法O(n m)O(1)仅小写字母差异计数法O(n m)O(1)仅小写字母哈希表 validO(n m)O(k)任意字符集