题目解析

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

算法讲解

寻找目标串的异位词，我们使用固定长度的滑动窗口，首先我们判断窗口左右的字符是否存在于目标串中，如果不存在就让窗口滑动；存在的话，我们就把字符丢进Hash中，判断是否是子串，如果是子串放入结果中，不是的话还是移动窗口

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int Hash[26] = {0};
        int Hash_p[26] = {0};
        //滑动窗口大小固定
        int left = 0, right = p.size()-1;
        //确定p中的字符
        for(auto& ch : p)
        {
            Hash_p[ch - 'a']++;
        }
        int count = 0;
        int begin = left;
        while(right < s.size())
        {
            //当前左右窗口的字符如果没有出现在p中就跳过本次循环
            if(Hash_p[s[left] - 'a'] == 0 || Hash_p[s[right] - 'a'] == 0)
            {
                left++;
                right++;
                continue;
            }
            count = 0;
            begin = left;
            memset(Hash, 0, sizeof(Hash));
            while(begin <= right)
            {
                if(Hash_p[s[begin] - 'a'] == 0)break;
                //添加异位词
                if(Hash[s[begin] - 'a'] < Hash_p[s[begin] - 'a'])
                {
                    Hash[s[begin] - 'a']++;
                    count++;
                }
                if(count == p.size())
                {
                    ret.push_back(left);
                    break;
                }
                begin++;
            }
            left++;
            right++;
        }
        return ret;
    }
};