算法014——找到字符串中所有字母异位词

（点击跳转）

如果 P = “abc”，那么下图中的都是它的异位词。

在 S 中找到 P 的异位词后，要返回起始位置的下标。

做这道题之前，我们要知道如何判断两个字符串是否是异位词，其实我们可以统计每个字符出现的次数，如果两个字符串中每个字符出现的次数相等，那么他们就是异位词。利用哈希表即可

我们定义一个变量 m 表示 p 字符串的长度，我们将 p 字符串中字母出现的次数存放在 hash1 中，在 s 这个字符串中，找到长度为 m 的子串 ，将次数存放到 hash2 中，然后比较两个哈希表是否相等就可以。

其实我们没有必要每次都将 m 个字母的次数都存放在哈希表中 ，如下图所示，红色为第一次枚举放入到哈希表中，粉色为第二次枚举放入到哈希表中，被荧光笔涂到的区域其实已经在哈希表中了，没必要再次存放， 只需要将 c 从哈希表中删除，在将 e 添加到哈希表中即可 。

所以，我们可以使用滑动窗口的方法来解决此问题。

1. left = 0,right = 0

2. 进窗口 ：hash2[in]++

3. 判断 ：right - left + 1 > m

   出窗口 ：hash2[out]–

   更新结果 :check(hash1,hash2)（比较两个哈希表是否相等）

在更新结果当中，我们需要遍历两个哈希表来进行check，比较麻烦，所以我们对更新结果的判断条件进行优化。

我们定义一个变量 count 来统计 窗口 中 有效字符 的个数

如下图所示，当 c 进入窗口之后，与 hash1 中 c 字符出现的次数比较，有两种清情况。

1. 小于等于 hash1 中的……，说明 c 为有效字符，让 count + 1

   

   之后 right 继续右移，然后放入到 hash2 中

2. 大于 hash1 中的……，count 不更新

   

   接下来，right 右移

   

   right 继续右移

   

此时，窗口大于 m ，让 left 右移，再将第一个 c 从 hash2 中删除之前，我们要先判断此时这个字符出现的次数是否大于 hash1 中的次数，这种情况，显然是大于，那么删掉的就是无效字符，count 不需要变化，此时 c 的个数变成了 1。

然后我们再判断 count是否等于m，此时count == m，那么窗口中的字符就是 p 的异位词，输出起始位置下标

接下来的遍历就省略了

1. 进窗口 ：hash2[in] <= hash1[in] ——> count++
2. 出窗口 ：hash2[out] <= hash1[out] ——> count–
3. 更新结果 ：count==m

代码如下：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();
        int[] hash1 = new int[26];
        for(char ch : p1){
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        int m = p.length();
        for(int left = 0,right = 0,count = 0;right < s1.length;right++){
            char in = s1[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']){
                count++;
            }
            if(right - left + 1 > m){
                char out = s1[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']){
                    count--;
                }
            }
            if(count == m){
                ret.add(left);
            }
        }
        return ret;
    }
}

今日任务完成，嘻嘻