LeetCode：438. 找到字符串中所有字母异位词

简介题目链接https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/解决方式字符串 暴力枚举 / 滑动窗口、哈希表 / 数组这是作者学习众多大神的思路进行解题的步骤很推荐大家解题的时候去看看题解里面大佬们的思路、想法暴力枚举思路迭代每一个元素取目标字符串大小的子串统计字符出现的频率。若频率相同则添加其实索引若不通继续迭代下一个元素直至迭代到还剩字符串大小的字串。publicclassSolution{publicListIntegerfindAnagrams(Strings,Stringp){ListIntegerresultnewArrayList();intsLens.length();intpLenp.length();if(sLenpLen){returnresult;}// 统计 p 的字符频率int[]pCountnewint[26];for(charc:p.toCharArray()){pCount[c-a];}// 遍历 s 中所有可能的子串for(inti0;isLen-pLen;i){int[]subCountnewint[26];// 统计当前子串的字符频率for(intji;jipLen;j){subCount[s.charAt(j)-a];}// 比较频率数组if(matches(pCount,subCount)){result.add(i);}}returnresult;}// 辅助方法比较两个频率数组是否相等privatebooleanmatches(int[]a,int[]b){for(inti0;i26;i){if(a[i]!b[i]){returnfalse;}}returntrue;}}这种方式有两个问题。一字符频率比较是循环迭代挨个对比比较慢。二外层循环迭代下一个元素时每次都会重新开始计算字符频率但是实际窗口中变化的字符只有窗口左右两端其它都是相同的存在大量重复计算。下面的滑动窗口就是针对这两个问题进行的优化。滑动窗口思路这题的思路与76.最小覆盖子串题目类似都是使用滑动窗口然后通过哈希表或数组第三方数据结构判断滑动窗口的扩大、收缩时机。不一样的是收缩条件变为滑动窗口的长度等于目标的长度。在这种情况下valid 变量等于所需字符种类数相当于固定长度长度等于目标的滑动窗口包含了所有目标字符种类且满足数量该窗口字串就是目标的排列或字母异味词了。哈希表推荐查看labuladong大佬的题解classSolution{publicListIntegerfindAnagrams(Strings,Stringp){// 哈希表所需的字符种类和数量HashMapCharacter,IntegerneednewHashMap();for(inti0;ip.length();i){charcp.charAt(i);need.put(c,need.getOrDefault(c,0)1);}// 哈希表滑动窗口中对于的哈希值HashMapCharacter,IntegerwindownewHashMap();// 双指针intleft0;intright0;// 滑动窗口中满足目标字符的个数intvalid0;// 结果ArrayListIntegerlistnewArrayList();// 迭代while(rights.length()){// 当前字符charcs.charAt(right);// 滑动窗口扩大right;// 判断if(need.containsKey(c)){// 当前元素是目标字符加入滑动窗口对于的字符哈希表中window.put(c,window.getOrDefault(c,0)1);if(window.get(c).equals(need.get(c))){// 滑动窗口中的该字符满足目标valid;}}// 滑动窗口保持固定大小移动缩小while(right-leftp.length()){if(validneed.size()){// 大小一致目标字符种类数量也满足当前子串就是异位词list.add(left);}// 左边界移动charclefts.charAt(left);left;// 元素为目标字符if(need.containsKey(cleft)){if(window.get(cleft).equals(need.get(cleft))){valid--;}window.put(cleft,window.getOrDefault(cleft,0)-1);}}}// 返回结果returnlist;}}数组推荐查看灵茶山艾府大佬的题解classSolution{// 滑动窗口// 大体思路是有两个数组一个代表滑动窗口一个代表目标字符串滑动窗口的大小于与目标字符串相同// 移动滑动窗口比较两数组是否相同。相同则表示寻找到目标的字母异位体因为两者的字符、数量相同publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length(),pLenp.length();// 特例判断if(sLenpLen){returnnewArrayListInteger();}// 初始化数组和结果集ArrayListIntegeransnewArrayList();int[]sCountnewint[26];int[]pCountnewint[26];// 初始化滑动窗口for(inti0;ipLen;i){// 字符与数组索引映射sCount[s.charAt(i)-a];pCount[p.charAt(i)-a];}if(Arrays.equals(sCount,pCount)){ans.add(0);}// 移动滑动窗口// 此时i 代表滑动窗口的左边界以及 s 中剩下的字符即滑动窗口需要移动的次数for(inti0;isLen-pLen;i){// 去除左边界元素--sCount[s.charAt(i)-a];// 滑动窗口向右移动sCount[s.charAt(ipLen)-a];// 判断if(Arrays.equals(sCount,pCount)){// 初始位置为左边界 1ans.add(i1);}}returnans;}}另一种写法classSolution{publicListIntegerfindAnagrams(Strings,Stringp){// 结果集合ArrayListIntegerlistnewArrayList();// 边界处理if(s.length()p.length())returnlist;// 双指针intleft0;intright0;// 目标字符种类和数量int[]neednewint[26];// 滑动窗口中的字符种类和数量int[]windownewint[26];// 滑动窗口中满足目标字符种类数量的差异计数intdiff0;// 第一个字串对比for(inti0;ip.length();i){need[p.charAt(i)-a];window[s.charAt(i)-a];}for(inti0;i26;i){if(need[i]window[i])diff;}if(diff26){list.add(0);}// 后续迭代for(rightp.length();rights.length();right){//滑动窗口右边界扩大charcs.charAt(right);window[c-a];if(window[c-a]need[c-a]){// 当前字符为目标字符且添加后数量一致diff;}elseif(window[c-a]need[c-a]1){// 当前字符无目标字符但是添加后数量多一// 或// 当前字符不是目标字符且原先并不存在diff--;}// 滑动窗口左边界缩小charclefts.charAt(left);left;window[cleft-a]--;if(window[cleft-a]need[cleft-a]){// 当前字符为目标字符且减去后数量一致// 或// 当前字符非目标字符且1️已完全去除diff;}elseif(window[cleft-a]need[cleft-a]-1){// 当前字符为目标字符但是减去后数量少一diff--;}// 差异计数判断是否是异位词if(diff26)list.add(left);}// 返回结果returnlist;}}