Leetcode|滑动窗口|438. 找到字符串中所有字母异位词

1 滑动窗口

代码语言：javascript复制

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.empty()) return {};
        unordered_map<char, int> need, window;
        for (auto& c : p) need[c]  ;
        int left = 0, right = 0, vaild = 0;
        int len = p.size();
        vector<int> start;
        while (right < s.size()) {
            char in = s[right];
            right  ;
            if (need.count(in)) {
                window[in]  ;
                if (window[in] == need[in]) vaild  ;
            }
            while (vaild == need.size()) {
                // 基于滑动窗口模板修改处
                if (right - left == len) start.push_back(left);
                char out = s[left];
                left  ;
                if (window.count(out)) {
                    if (window[out] == need[out]) vaild--;
                    window[out]--;
                }
            }
        }
        return start;
    }
};

leetcode

0 人点赞