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

思路：滑动窗口。

对于主串s和子串p，设n是子串p的长度。

一、方法一：定长滑动窗口。枚举主串s的所有长为n的子串s'，在滑动的同时维护s’中的每种字母的出现次数。如果s'的每种字母的出现次数和p的每种字母的出现次数都相同，那么s'是p的异位词，并把s'的左端点下标加入答案。

附代码：

class Solution { public List<Integer> findAnagrams(String s, String p) { //统计p的每种字母的出现次数 int[] cntp = new int[26]; for(char c : p.toCharArray()){ cntp[c - 'a']++; //统计p的字母 } List<Integer> res = new ArrayList<>(); int[] cnts = new int[26]; //统计s的长度为p.length()的子串s'的每种字母的出现次数 for(int right = 0;right < s.length();right++){ cnts[s.charAt(right) - 'a']++; //右端点字母进入窗口 int left = right - p.length() + 1; if(left < 0){ //窗口长度不足p.length() continue; } if(Arrays.equals(cnts,cntp)){ //s'和p的每种字母的出现次数都相同 res.add(left); //s'的左端点下标加入答案 } cnts[s.charAt(left) - 'a']--; //左端点字母离开窗口 } return res; } }

二、方法二：不定长滑动窗口。枚举子串s'的右端点，如果发现s’其中一种字母的出现次数大于p的这种字母的出现次数，则右移s'的左端点（缩小窗口）。如果发现s'的长度等于p的长度，则说明s'的每种字母的出现次数等于p的每种字母的出现次数，即s'是p的异位词。

证明：内层循环结束后，s'的每种字母的出现次数都小于等于p的每种字母的出现次数。如果s’的其中一种字母的出现次数比p的小，那么s'的长度必然小于p的长度。所以只要s'的长度等于p的长度，就说明s'的每种字母的出现次数和p的每种字母的出现次数都相同，就说明s'是p的异位词，于是把s'的左端点下标加入答案。

代码实现时，可以把cnts和cntp合并成一个cnt：

（1）对于p的字母c，把cnt[c]加一。

（2）对于s的字母c，把cnt[c]减一。

（3）如果cnt[c]小于0，则说明窗口中的字母c的个数比p的多，右移左端点。

附代码：

class Solution { public List<Integer> findAnagrams(String s, String p) { //统计p的每种字母的出现次数 int[] cnt = new int[26]; for(char c : p.toCharArray()){ cnt[c - 'a']++; } List<Integer> res = new ArrayList<>(); int left = 0; for(int right = 0;right < s.length();right++){ int c = s.charAt(right) - 'a'; cnt[c]--; //右端点字母进入窗口 while(cnt[c] < 0){ //字母c太多了 cnt[s.charAt(left) - 'a']++; //左端点字母离开窗口 left++; } if(right - left + 1 == p.length()){ //s'和p的每种字母的出现次数都相同 res.add(left); //s'的左端点下标加入答案 } } return res; } }