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

简介

题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

解决方式：字符串 + 暴力枚举 / 滑动窗口、哈希表 / 数组

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

暴力枚举

思路：迭代每一个元素，取目标字符串大小的子串，统计字符出现的频率。若频率相同则添加其实索引，若不通继续迭代下一个元素，直至迭代到还剩字符串大小的字串。

publicclassSolution{publicList<Integer>findAnagrams(Strings,Stringp){List<Integer>result=newArrayList<>();intsLen=s.length();intpLen=p.length();if(sLen<pLen){returnresult;}// 统计 p 的字符频率int[]pCount=newint[26];for(charc:p.toCharArray()){pCount[c-'a']++;}// 遍历 s 中所有可能的子串for(inti=0;i<=sLen-pLen;i++){int[]subCount=newint[26];// 统计当前子串的字符频率for(intj=i;j<i+pLen;j++){subCount[s.charAt(j)-'a']++;}// 比较频率数组if(matches(pCount,subCount)){result.add(i);}}returnresult;}// 辅助方法：比较两个频率数组是否相等privatebooleanmatches(int[]a,int[]b){for(inti=0;i<26;i++){if(a[i]!=b[i]){returnfalse;}}returntrue;}}

这种方式有两个问题。一，字符频率比较是循环迭代挨个对比，比较慢。二，外层循环迭代下一个元素时，每次都会重新开始计算字符频率，但是实际窗口中变化的字符只有窗口左右两端，其它都是相同的，存在大量重复计算。

下面的滑动窗口就是针对这两个问题进行的优化。

滑动窗口

思路：这题的思路与76.最小覆盖子串题目类似，都是使用滑动窗口然后通过哈希表或数组第三方数据结构判断滑动窗口的扩大、收缩时机。不一样的是，收缩条件变为滑动窗口的长度等于目标的长度。在这种情况下，valid 变量等于所需字符种类数，相当于固定长度（长度等于目标）的滑动窗口包含了所有目标字符种类且满足数量，该窗口字串就是目标的排列或字母异味词了。

哈希表

推荐查看labuladong大佬的题解！

classSolution{publicList<Integer>findAnagrams(Strings,Stringp){// 哈希表，所需的字符种类和数量HashMap<Character,Integer>need=newHashMap();for(inti=0;i<p.length();i++){charc=p.charAt(i);need.put(c,need.getOrDefault(c,0)+1);}// 哈希表，滑动窗口中对于的哈希值HashMap<Character,Integer>window=newHashMap();// 双指针intleft=0;intright=0;// 滑动窗口中满足目标字符的个数intvalid=0;// 结果ArrayList<Integer>list=newArrayList();// 迭代while(right<s.length()){// 当前字符charc=s.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-left==p.length()){if(valid==need.size()){// 大小一致，目标字符种类数量也满足，当前子串就是异位词list.add(left);}// 左边界移动charcleft=s.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{// 滑动窗口// 大体思路是有两个数组，一个代表滑动窗口，一个代表目标字符串，滑动窗口的大小于与目标字符串相同// 移动滑动窗口，比较两数组是否相同。相同则表示寻找到目标的字母异位体，因为两者的字符、数量相同publicList<Integer>findAnagrams(Strings,Stringp){intsLen=s.length(),pLen=p.length();// 特例判断if(sLen<pLen){returnnewArrayList<Integer>();}// 初始化数组和结果集ArrayList<Integer>ans=newArrayList<>();int[]sCount=newint[26];int[]pCount=newint[26];// 初始化滑动窗口for(inti=0;i<pLen;i++){// 字符与数组索引映射++sCount[s.charAt(i)-'a'];++pCount[p.charAt(i)-'a'];}if(Arrays.equals(sCount,pCount)){ans.add(0);}// 移动滑动窗口// 此时，i 代表滑动窗口的左边界以及 s 中剩下的字符，即滑动窗口需要移动的次数for(inti=0;i<sLen-pLen;i++){// 去除左边界元素--sCount[s.charAt(i)-'a'];// 滑动窗口向右移动++sCount[s.charAt(i+pLen)-'a'];// 判断if(Arrays.equals(sCount,pCount)){// 初始位置为左边界 + 1ans.add(i+1);}}returnans;}}

另一种写法

classSolution{publicList<Integer>findAnagrams(Strings,Stringp){// 结果集合ArrayList<Integer>list=newArrayList<>();// 边界处理if(s.length()<p.length())returnlist;// 双指针intleft=0;intright=0;// 目标字符种类和数量int[]need=newint[26];// 滑动窗口中的字符种类和数量int[]window=newint[26];// 滑动窗口中满足目标字符种类数量的差异计数intdiff=0;// 第一个字串对比for(inti=0;i<p.length();i++){need[p.charAt(i)-'a']++;window[s.charAt(i)-'a']++;}for(inti=0;i<26;i++){if(need[i]==window[i])diff++;}if(diff==26){list.add(0);}// 后续迭代for(right=p.length();right<s.length();right++){//滑动窗口右边界扩大charc=s.charAt(right);window[c-'a']++;if(window[c-'a']==need[c-'a']){// 当前字符为目标字符且添加后数量一致diff++;}elseif(window[c-'a']==need[c-'a']+1){// 当前字符无目标字符，但是添加后数量多一// 或// 当前字符不是目标字符且原先并不存在diff--;}// 滑动窗口左边界缩小charcleft=s.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(diff==26)list.add(left);}// 返回结果returnlist;}}