题解 | #坐标移动#

滑动窗口，蛮不错的一个方法

记录下来，可能会用到的

class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
string minWindow(string S, string T) {
    int left = 0, right = 0;
    int start = 0, minlen = INT_MAX;
    unordered_map<char, int> need;
    unordered_map<char, int> windows;

    for(auto i : T) need[i]++;
    int match = 0;

    while(right < S.length()) {
        char k = S[right];
        //元素S[i]在need数组中存在
        if(need.count(k)) {
            // windows[k]先++
            windows[k]++;
            // 这是考虑到同一个字符元素可能用多个的情况，例如T中有两个a
            if(windows[k] == need[k]) match++;
        }
        right++;
        while(match == need.size()) {
            if(right - left < minlen){
                minlen = right - left;
                start = left;
            }
            char m = S[left];
            if(need.count(m)) {
                windows[m]--;
                if(windows[m] < need[m]) match--;
            }
            left++;
        }

    }
    return minlen == INT_MAX ? "" : S.substr(start, minlen);
}
};