438. Find All Anagrams in a String

438. Find All Anagrams in a String

sliding window大佬归纳

滑动窗口

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> map;
        for(auto ch : p)
            ++map[ch];
        int count = map.size();
        vector<int> ret;
        int begin = 0, end = 0, n = s.size(), m = p.size();
        while(end < n)
        {
            if(map.count(s[end]) && --map[s[end]] == 0)
                --count;
            while(count == 0)
            {
                if(end - begin + 1 == m)
                    ret.push_back(begin);
                if(map.count(s[begin]) && ++map[s[begin]] > 0)
                    ++count;
                ++begin;
            }
            ++end;
        }
        return ret;

    }
};

review

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> map;
        for(auto ch : p)
            ++map[ch];
        int count = map.size();
        vector<int> ret;
        int begin = 0, end = 0, n = s.size(), m = p.size();
        while(end < n)
        {
            if(--map[s[end]] == 0) // 如果s[end]不在map中，减的结果会是小于0，不会影响count的计数，而且这个map中减去的最后会随着窗口滑动而重新归零
                --count;
            while(count == 0)
            {
                if(end - begin + 1 == m) // count是0了，且长度符合，所以是解
                    ret.push_back(begin);
                if(++map[s[begin++]] > 0) // 这里没有判定s[begin]是不是在map中，如果不在count中，随着窗口的滑动，他顶多归零，不会影响到count
                    ++count;
            }
            ++end;
        }
        return ret;

    }
};