LeetCode 438：找到字符串中所有字母异位词——定长窗口 + 欠债种类数

题目描述给定两个字符串s和p找到s中所有p的异位词子串返回这些子串的起始索引。答案顺序任意。异位词字符种类相同每个字符出现次数也相同只是顺序可以不同。例如s cbaebabacdp abc的答案是[0, 6]。最初思路方向是对的用int[128]做频次数组再在s上滑一个长度等于|p|的窗口。第一版额外维护了三个变量cnt当前窗口里已经放了几个字符len还没凑齐的量l左端下标右端i每进来一个字符就a[c]--a[c] 0时len--。然后用两套条件决定要不要从左边弹出窗口已经合法len 0或者窗口已经满长cnt p.length()。问题出在哪里同一轮里两套出窗逻辑可能各执行一次。改成else if之后abab/ab能得到[0, 1, 2]但根因还在。cnt在匹配成功后没有回到「当前窗口的真实长度」。以官方用例为例s cbaebabacd p abc下标0..2的cba是合法窗口。下一轮i 3进来的是e它不在p里窗口已经非法左端却不会继续往右缩e会留在窗口里。另外len一开始按p.length()用个数初始化真正改len时却只在a[c] 0时加减问的是种类刚凑齐或出窗后刚从齐变成缺。个数和种类混在同一个变量里。出窗时还容易把a[s1[left]] 0理解成「左端这个字母是不是p里要找的」。s aabp ab走到窗口aa时左端a确实是要找的字母但当时a[a]并不是0。这个判断真正在问这一类现在是不是刚好凑齐拆掉它之后会不会从「齐」变成「缺」。正确思路先固定一个核心不变量每次判断答案时候选窗口的长度必须恰好等于|p|。右端下标是i时候选窗口的左端为left i - p.length() 1当left 0说明窗口已经达到|p|先判断它是否为异位词再把s[left]移出为下一轮腾位置。因此不需要单独维护l和cnt。频次数组a可以理解为一张「欠债表」a[c]表示窗口还欠p多少个字符c正数窗口里还缺这个字符0数量刚好负数这个字符进多了或者它根本不在p中len只记录「还没凑齐的字符种类数」。初始化时p中每出现一种新字符len。进窗、出窗时只有某个种类在「缺」和「齐」之间切换才修改len。当候选窗口长度等于|p|且len 0时窗口就是异位词。因为所有必需字符都已凑齐而窗口总长度又没有多余位置不可能再混入其他字符。窗口含义每轮要判断的候选窗口是s[left .. i]。在窗口尚未达到|p|时只让字符进窗达到|p|后先判断当前窗口再移出左端字符。扩张与收缩时机扩张右端字符c s1[i]进窗先执行a[c]--。若减完刚好等于0说明这个字符种类从「还缺」变成「刚好」所以len--。收缩当left 0时先判断当前窗口再移出s1[left]。如果移出前a[s1[left]] 0说明这一类原本数量刚好移出后会重新缺一个所以先len再执行a[s1[left]]。这样每轮只进一个字符并在窗口满后只出一个字符。遇到e这种无关字符时它的欠债值会变成负数窗口仍会持续向右滑动直到它被移出。窗口内维护什么只维护欠债表a和欠债种类数len。多进来的字符、不在p里的字符都走负数不会误伤len。原来的cnt没有参与这套不变量可以删掉。手推过程s cbaebabacdp abc。一开始a[a]a[b]a[c]1len 3。i0 进 ca[c]0len2窗口未满 i1 进 ba[b]0len1窗口未满 i2 进 aa[a]0len0left0 记 0出 ca[c] 从 0 变 1len1 i3 进 ea[e]-1len 仍为 1left1 不出答案出 ba[b] 从 0 变 1len2e进来后窗口非法但左端仍会跟着右端移动不会停住。继续滑动到i 8时候选窗口是下标6..8的baclen再次变为0所以记录起点6。最终答案是[0, 6]。再看s aabp ab用来区分「是不是要找的字母」和「这一类是否刚好齐」i0 进 aa[a]0len1窗口未满 i1 进 aa[a]-1len 仍为 1left0 候选窗口是 aa不能记答案 出左端 a此时 a[a]-1不是 0len 不变 再执行 a[a]a[a] 变回 0 i2 进 ba[b]0len0left1 候选窗口是 ab记录起点 1左端那个a虽然属于p但在窗口aa中它是多出来的那个。出窗是否修改len取决于这一类在出窗前是否数量刚好而不是这个字符是否属于p。伪代码下面的伪代码与紧接的 Java 实现逐步对应统计欠债种类、进窗、窗口满后判定、出窗。函数 findAnagrams(s, p): ans - 空列表 a - 长度为 128 的数组初值 0 len - 0 对于 p 中的每个字符 c: 如果 a[c] 0: len - len 1 a[c] - a[c] 1 s1 - s 的字符数组 对于 i 从 0 到 s1.length - 1: a[s1[i]] - a[s1[i]] - 1 如果 a[s1[i]] 0: len - len - 1 left - i - p.length 1 如果 left 0: 如果 len 0: 把 left 加入 ans 如果 a[s1[left]] 0: len - len 1 a[s1[left]] - a[s1[left]] 1 返回 ansJava 代码对应实现只做了排版并去掉不参与逻辑的cntimport java.util.ArrayList; import java.util.List; class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger ans new ArrayList(); int[] a new int[128]; int len 0; for (char c : p.toCharArray()) { if (a[c] 0) len; a[c]; } char[] s1 s.toCharArray(); for (int i 0; i s1.length; i) { a[s1[i]]--; if (a[s1[i]] 0) { len--; } int left i - p.length() 1; if (left 0) { if (len 0) { ans.add(left); } if (a[s1[left]] 0) { len; } a[s1[left]]; } } return ans; } }易错点同一轮不要既按「已经合法」出窗又按「已经满长」再出一次定长写法里进出窗口各一次就够了。遇到不在p中的字符窗口必须继续保持定长往前滑不能只右移一格就停。len要么始终表示还欠的种类要么始终表示还欠的个数不要混用。当前实现是种类进窗后 0才len--出窗前 0才len。a[s1[left]] 0不是在问「它是不是要找的字母」而是在问「这一类现在是否刚好齐」。先判定len 0再出窗。先出窗会把当前合法窗口拆掉答案会漏。没有参与不变量的变量本轮的cnt不要留在最终代码里。建议测试用例s cbaebabacd, p abc 期望[0, 6] 说明中间夹着不在 p 里的 e检查窗口会不会卡住s abab, p ab 期望[0, 1, 2] 说明连续重叠的合法窗口s aab, p ab 期望[1] 说明窗口 aa 中有多余的 a检查出窗时是否错误修改 lens aa, p aa 期望[0] 说明p 里有重复字符s af, p be 期望[] 说明字符种类完全不相交s a, p a 期望[0] 说明最短合法窗口复杂度分析时间复杂度O(|s| |p|)。初始化扫描一次p之后s中的每个字符进窗一次、出窗至多一次。空间复杂度欠债表int[128]是O(1)Java 实现中的toCharArray()会复制s因此整段代码的额外空间为O(|s|)。复盘本轮从「lcnt 两套出窗条件」收成「定长窗口 欠债种类数」。最值得记住的是a[c] 0描述的是种类刚齐或刚缺不是「这个字母在不在p里」非法字符靠负数和定长出窗自然被滑走。正确性可以用cbaebabacd里的e以及aab/ab时多余的a自检。