（算法）找到字符串中所有字母异位词——＜滑动窗⼝+哈希表＞

1. 题⽬链接：438.找到字符串中所有字⺟异位词

2. 题⽬描述：

3. 解法（滑动窗⼝+哈希表）： 

算法思路：

◦ 因为字符串p 的异位词的⻓度⼀定与字符串p 的⻓度相同，所以我们可以在字符串s 中构造⼀个⻓度为与字符串p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量； 

◦ 当窗⼝中每种字⺟的数量与字符串p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串p 的异位词；

◦ 因此可以⽤两个⼤⼩为26 的数组来模拟哈希表,⼀个来保存s 中的⼦串每个字符出现的个数，另⼀个来保存p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。

C++算法代码： 

#include<iostream> 
#include<string>
#include<vector>
using namespace std;
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        int hash1[26] = { 0 };  //记录字符串1子串中元素的出现次数
        int hash2[26] = { 0 };  //记录字符串2中元素的出现次数
        vector<int>vt;  //记录子串的起始索引
        //初始化字符串2中元素的出现次数
        for (int i = 0; i < p.size(); i++)
        {
            hash2[p[i] - 'a']++;
        }
        int left = 0, right = 0;
        int count = 0;    //满足条件的元素数目
        while (right < s.size())
        {
            //如果元素个数满足条件则计数器加1
            if (++hash1[s[right] - 'a'] <= hash2[s[right] - 'a'])
            {
                count++;
            }
            //出窗口
            if (right - left + 1 > p.size())
            {
                //退窗口
                hash1[s[left] - 'a']--;
                //不满足条件了则满足条件数-1
                if (hash1[s[left] - 'a'] < hash2[s[left] - 'a'])
                {
                    count--;
                }
                left++;
            }
            //记录
            //当满足条件数==目标子串大小则记录
            if (count == p.size())
            {
                vt.push_back(left);
            }
            right++;
        }
        return vt;
    }
};

Java算法代码：

class Solution
{
	public List<Integer> findAnagrams(String ss, String pp)
	{
		List<Integer> ret = new ArrayList<Integer>();
		char[] s = ss.toCharArray();
		char[] p = pp.toCharArray();
		int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数 
		for (char ch : p) hash1[ch - 'a']++;
		int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数 
		int m = p.length;
		for (int left = 0, right = 0, count = 0; right < s.length; right++)
		{
			char in = s[right];
			// 进窗⼝ + 维护 count 
			if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
			if (right - left + 1 > m) // 判断 
			{
				char out = s[left++];
				// 出窗⼝ + 维护 count 
				if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
			}
			// 更新结果 
			if (count == m) ret.add(left);
		}
		return ret;
	}
}