力扣hot100-438.找到字符串中所有字母异位词-固定长度滑动窗口详解

LeetCode 438. 找到字符串中所有字母异位词固定长度滑动窗口详解1. 这道题到底在问什么LeetCode 438「找到字符串中所有字母异位词」的题意是给定两个字符串 s 和 p找到 s 中所有 p 的异位词子串返回这些子串的起始索引。这句话里有三个关键词1. 子串 2. 异位词 3. 起始索引先看“子串”。子串必须是连续的。比如s cbaebabacd p abccba是s的子串因为它连续出现在下标0到下标2。bac也是s的子串因为它连续出现在下标6到下标8。再看“异位词”。两个字符串如果字符种类相同并且每种字符出现次数也相同只是顺序不同那么它们就是字母异位词。例如abc bac cba它们都是彼此的异位词因为它们都有a 出现 1 次 b 出现 1 次 c 出现 1 次顺序不重要字符数量才重要。所以这道题可以翻译成更直白的话在 s 中找所有长度等于 p.length() 的连续子串 只要这个子串的字符出现次数和 p 完全一样就记录它的起始下标。2. 为什么这题适合滑动窗口这题和 LeetCode 3「无重复字符的最长子串」一样都是字符串上的连续区间问题。但是两题的窗口特点不同。第 3 题是窗口长度不固定。 条件是窗口内不能有重复字符。 目标是求最长长度。第 438 题是窗口长度固定。 窗口长度永远等于 p.length()。 条件是窗口字符计数必须和 p 完全一样。 目标是找出所有满足条件的起始下标。因为p的异位词长度一定和p一样所以我们不需要考虑长度不同的子串。假设p abc那么p.length() 3。我们只需要检查s中所有长度为3的窗口s[0..2] s[1..3] s[2..4] ...这正好是固定长度滑动窗口。窗口每次向右移动一格只发生两件事1. 左边出去一个字符 2. 右边进来一个字符所以我们可以维护窗口内每个字符的出现次数不需要每次重新统计整个子串。3. 第一性原理异位词本质是字符计数相同这题最核心的判断不是字符串顺序而是字符出现次数。比如p aab那么它的异位词必须满足a 出现 2 次 b 出现 1 次所以aba 是异位词 baa 是异位词 abb 不是异位词因为 a 少了b 多了 abc 不是异位词因为 a 少了一个还多了 c因此对于任意一个窗口我们只需要问一个问题当前窗口中每个字母出现的次数是否和 p 中每个字母出现的次数完全一样如果一样当前窗口就是p的异位词。如果不一样就不是。题目中的字符是小写英文字母所以可以用长度为26的数组统计字符次数。int[]neednewint[26];int[]windownewint[26];含义是need 记录 p 中每个字母出现多少次 window 记录当前窗口中每个字母出现多少次数组下标和字母的对应关系是0 - a 1 - b 2 - c ... 25 - z所以某个字符ch对应的下标是ch-a例如a-a0b-a1c-a24. 核心算法流程设n s.length() m p.length()因为窗口长度固定为m所以算法流程可以分成几步1. 如果 n m说明 s 比 p 还短不可能存在答案直接返回空列表。 2. 统计 p 的字符次数放入 need。 3. 统计 s 的第一个长度为 m 的窗口放入 window。 4. 比较 need 和 window如果一样记录起始下标 0。 5. 之后窗口不断向右滑动 - 右边新字符进入窗口 - 左边旧字符离开窗口 - 比较 need 和 window - 如果一样记录当前窗口起始下标这就是固定长度滑动窗口的标准形态。5. Java 代码完整注释importjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;classSolution{publicListIntegerfindAnagrams(Strings,Stringp){// ans 用来保存所有符合条件的起始下标。ListIntegeransnewArrayList();// n 是字符串 s 的长度。intns.length();// m 是字符串 p 的长度。// p 的异位词长度一定等于 m所以滑动窗口长度固定为 m。intmp.length();// 如果 s 比 p 还短那么 s 中不可能存在 p 的异位词子串。if(nm){returnans;}// need 统计 p 中每个字符出现的次数。// window 统计当前滑动窗口中每个字符出现的次数。//// 题目只包含小写英文字母所以数组长度为 26。// 下标 0 表示 a下标 1 表示 b以此类推。int[]neednewint[26];int[]windownewint[26];// 初始化 need 和第一个窗口 window。// 第一个窗口是 s[0..m-1]长度正好等于 p.length()。for(inti0;im;i){// 统计 p 中字符出现次数。need[p.charAt(i)-a];// 统计 s 的第一个窗口中字符出现次数。window[s.charAt(i)-a];}// 判断第一个窗口是否是 p 的异位词。// 如果 need 和 window 两个数组完全相同说明每个字母出现次数都一样。if(Arrays.equals(need,window)){ans.add(0);}// 从下标 m 开始窗口向右滑动。//// right 表示当前要进入窗口的新字符下标。// 因为前面已经处理了 s[0..m-1]所以下一个进入窗口的是 s[m]。for(intrightm;rightn;right){// 右边新字符进入窗口。window[s.charAt(right)-a];// 左边旧字符离开窗口。//// 当前新加入的是 right为了保持窗口长度为 m// 需要移除下标 right - m 位置的字符。window[s.charAt(right-m)-a]--;// 当前窗口范围是 [right - m 1, right]。// 所以当前窗口的起始下标是 right - m 1。if(Arrays.equals(need,window)){ans.add(right-m1);}}// 返回所有异位词子串的起始下标。returnans;}}6. 用 cbaebabacd 手动模拟一遍用题目经典例子s cbaebabacd p abcp.length() 3所以窗口长度固定为3。先统计pneed: a: 1 b: 1 c: 1第一个窗口是s[0..2] cba这个窗口的字符计数是window: a: 1 b: 1 c: 1和need完全一样所以cba是abc的异位词。记录起始下标ans [0]接下来窗口向右移动一格。从cba变成bae发生了两件事出去 c 进来 e此时窗口计数变成a: 1 b: 1 e: 1它和need不一样因为need需要的是a、b、c但当前窗口里没有c多了e。所以不记录。继续滑动直到窗口来到s[6..8] bac它的字符计数是a: 1 b: 1 c: 1和need完全一样。所以记录起始下标6ans [0, 6]最终返回[0, 6]7. 为什么移除的是 right - m这行代码容易让人停一下window[s.charAt(right-m)-a]--;它的含义是窗口右边新加入了 s[right]为了保持窗口长度还是 m左边必须移除一个字符。窗口长度固定为m。当right进入窗口后当前窗口的右边界是right。如果窗口长度是m那么窗口左边界应该是right - m 1也就是说新窗口应该是s[right - m 1 .. right]那么被挤出去的旧字符就是新窗口左边界前面的那个位置right - m所以代码要减掉window[s.charAt(right-m)-a]--;举个具体例子。s cbaebabacd p abc m 3一开始窗口是s[0..2] cba现在right 3新字符是s[3] e加入e之后为了窗口长度仍然是3需要移除s[right - m] s[3 - 3] s[0] c新窗口就变成s[1..3] bae这就是right - m的来源。8. 关于复杂度产生的一些疑问为什么 Arrays.equals 之后还是 O(n)刷题时很容易对复杂度产生一个疑问每次窗口滑动后都调用 Arrays.equals(need, window) 这不是还要比较整个数组吗为什么时间复杂度还能写 O(n)这个问题问得非常关键因为它涉及复杂度分析里“常数”的理解。这里的数组长度固定是26。也就是说Arrays.equals(need,window)每次最多只比较26个整数。窗口最多滑动n - m 1次所以总比较次数大约是26 * (n - m 1)在大 O 复杂度里固定常数可以省略。所以O(26 * n) O(n)这并不是说Arrays.equals没有成本而是说它的成本是固定上限的常数级。如果字符集不是小写英文字母而是一个很大的字符集比如需要比较几万个字符的计数数组那么复杂度分析就不能随便把这个比较成本忽略掉。但在本题中题目限定了小写英文字母字符种类固定为26因此这个写法的时间复杂度可以认为是O(n)空间复杂度是O(26)也就是常数空间。换句话说这个版本不是“没有比较数组”而是每次比较的数组长度固定为 26所以整体仍然是线性时间。9. 能不能进一步优化可以。有些题解会维护一个变量例如diff或valid用来记录两个计数数组之间还有多少差异。这样每次窗口滑动时只更新进出窗口的两个字符不需要每次调用Arrays.equals比较整个数组。但是对这道题来说Arrays.equals int[26]已经足够清晰也足够高效。如果刚开始学习滑动窗口优先理解这个版本更好。因为它把问题拆得很直观p 有一个字符计数。 窗口有一个字符计数。 两个计数一样就说明窗口是 p 的异位词。复杂优化写法只是减少常数不改变这道题的本质。10. 总结这道题的第一性原理是异位词不看字符顺序只看每个字符出现次数是否完全相同。因为p的异位词长度一定等于p.length()所以我们只需要在s上维护一个固定长度窗口。窗口每次右移一格时右边进来一个字符 左边出去一个字符我们用两个长度为26的数组维护计数need 表示 p 的字符计数 window 表示当前窗口的字符计数当Arrays.equals(need,window)为true时说明当前窗口就是p的一个异位词记录窗口起始下标即可。这题可以记成一句话用长度为 p.length() 的固定滑动窗口扫描 s窗口字符计数等于 p 的字符计数时记录窗口起点。它和 LeetCode 3 的区别也可以顺手记一下LeetCode 3窗口长度不固定条件是窗口内不能有重复字符。 LeetCode 438窗口长度固定条件是窗口字符计数和 p 完全相同。理解了这个差异滑动窗口这类题就会清楚很多。