异位词

指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;。

示…找到字符串中所有字母异位词

的长度相同的滑动窗口并在滑动中维护窗口中每种字母的数量当窗口中每种字母的数量与字符串

优化思路

在上述方法的基础上我们不再分别统计滑动窗口和字符串中每种字母的数量而是统计滑动窗口和字符串

代码实现注解

ArrayList();//定义一个一维数组记录字母在两个字符串中出现的差值//cnt[x]

s与p中字母x出现次数相同

ms.length();//如果目标字符长度大于原始字符长度返回空数组if(nm){return

res;}//开始遍历数组创造窗口滑块p数组出现的字母数值加一S数组出现的字母数字减一。

//所以当cnt数组上的数值为0是代表在滑块中p和s出现该字母的频率一致for(int

i0;in-1;i){cnt[p.charAt(i)-a];cnt[s.charAt(i)-a]--;}//将P字符串中的最后一个字母读入cnt中cnt[p.charAt(n-1)-a];int

l0;//将S字符串中的n-1位置上的字母作为滑块的右边界//开始滑动窗口for(int

rn-1;rm;r){cnt[s.charAt(r)-a]--;int

o0;//随着右边界的右移判断新的右边界。

如果cnt数组上的数值为0那么o赋值为1for(int

j0;j26;j){ocnt[j]0?1:0;}//说明s和p的同一个字母出现频率相等if(o26){res.add(l);}//左边界向右移缩小窗口cnt[s.charAt(l)-a];}return

res;}