LeetCode力ボタンブラシ問題記録76.Minimum Window Substringテーマ+アルゴリズム解析+Cpp解答

GitHubリンク:https://github.com/WilliamWuLH/LeetCode
いいと思うなら⭐StarとFork❤
76.Minimum Window Substring
スライドウィンドウ:
スライドウィンドウの思想:二重ポインタ、左右ポインタはすべて0から始まり、右ポインタは合法的な有効区間を見つけることを担当し、左ポインタはこの合法的な有効区間を最適化することを担当する.

初期化時に左ポインタleftも右ポインタrightも0から始まり、leftとrightが挟む区間を「ウィンドウ」と呼ぶ.

右ポインタrightを右(末尾へ)に移動し、ウィンドウを拡大し、区間が合法かどうかを絶えず判断する(テーマの要求に合致する).

このときの区間が合法的であれば(要求に合致する「ウィンドウ」が見つかった)、右ポインタrightは移動を停止し、左ポインタleftは右(尾へ)に移動し始め、ウィンドウを縮小し、区間が合法的であるかどうかを絶えず判断し(問題の要求に合致する)、同時にこのときの最良の答えを更新する.

このときの区間が合法でない場合(問題の要求に合致しない)、左ポインタleftは移動を停止し、右ポインタrightが最右(末尾)に達するまで上記の第2ステップと第3ステップを繰り返し、アルゴリズムは終了する.
ポイント難点:

このときの区間が合法(問題の要求に合致する)かどうかをどのように判断しますか?このステップの処理は時間空間の複雑度の最適化に関係します.

この時点の最適な答えをどのように更新しますか?

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0,right = 0,match = 0;
        int start = -1,len = INT_MAX;
        map m;
        for(auto c : t)
            m[c]++;
        while(right < s.length()){
            if(--m[ s[right] ] >= 0)
                match++;
            right++;
            while(match == t.length()){
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                if(++m[ s[left] ] > 0)
                    match--;
                left++;
            }
        }
        return start == -1 ? "" : s.substr(start,len);
    }
};