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

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

思路🧐：

代码🔎：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hashs[26] = { 0 }; //s的哈希表
        int hashp[26] = { 0 }; //p的哈希表
        for(auto e : p)
            hashp[e - 'a']++;
        int count = 0;
        int len = p.size();
        vector<int> ret;
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            hashs[s[right] - 'a']++;
            //如果插入时，s的哈希表的字母次数小于等于p，则为有效插入，count++
            if(hashs[s[right] - 'a'] <= hashp[s[right] - 'a'])
                count++;
            //当左右边框距离大于p，表示后面不可能再出现异位词子串,则需要更新左边框
            if(right - left + 1 > len)
            {
                //删除时，s的哈希表的字母次数小于等于p，则为有效删除，count--
                if(hashs[s[left] - 'a'] <= hashp[s[left] - 'a'])
                    count--;
                hashs[s[left++] - 'a']--; //减去字母次数，移动左边框
            }
            if(count == len)
                ret.push_back(left);
        }
        return ret;
    }
};

时间复杂度：O(N) 空间复杂度：O(1)