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

简介

题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=problem-list-v2&envId=2cktkvj

解决方式：滑动窗口

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

滑动窗口

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{// 滑动窗口优化// 大体思路是维护一个数组和一个不同变量 differ，取代两个数组的全量比较publicList<Integer>findAnagrams(Strings,Stringp){intsLen=s.length(),pLen=p.length();// 特例判断if(sLen<pLen){returnnewArrayList<Integer>();}// 初始化数组和结果集ArrayList<Integer>ans=newArrayList<>();int[]count=newint[26];// 初始化滑动窗口for(inti=0;i<pLen;i++){// 字符与数组索引映射++count[s.charAt(i)-'a'];--count[p.charAt(i)-'a'];}// 记录当前窗口与目标字符种类不同的个数，检验是否找到字母异位体// 相同字符不同个数不重复计入intdiffer=0;for(intj=0;j<26;++j){if(count[j]!=0){++differ;}}if(differ==0){ans.add(0);}// 移动滑动窗口// 此时，i 代表滑动窗口的左边界以及 s 中剩下的字符，即滑动窗口需要移动的次数// 检验是否异位体，是通过判断 differ 是否为 0for(inti=0;i<sLen-pLen;i++){// 移动左边界// 左边界的变动会导致滑动窗口的字符发生变化// 需要判断会不会导致 differ 变化，即窗口找到异位体if(count[s.charAt(i)-'a']==1){--differ;}elseif(count[s.charAt(i)-'a']==0){++differ;}--count[s.charAt(i)-'a'];// 真正移动// 移动右边界// 右边界的变动也会导致滑动窗口的字符发生变化// 也需要判断会不会导致 differ 变化，即窗口找到异位体if(count[s.charAt(i+pLen)-'a']==-1){--differ;}elseif(count[s.charAt(i+pLen)-'a']==0){++differ;}++count[s.charAt(i+pLen)-'a'];// 真正移动// 判断if(differ==0){ans.add(i+1);}}returnans;}}