算法1

(遍历一次) $O(n)$

看到一个比较巧妙的解法，整体逻辑和76题一致
当s串遇到一个t串不包含的char， 将左指针移动到当前char的下一位
s = “aoboba”
t = “ab”
hs[o] > ht[o] : j = 1, i = 2 (“包含o的子串一定无法生成排列”)

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    bool checkInclusion(string t, string s) {
        unordered_map<char, int> hs, ht; 

        for(auto& c : t) ht[c] ++;

        for(int i = 0, j = 0; j < s.size(); j ++ ) {
            hs[s[j]] ++;

            while(hs[s[j]] > ht[s[j]]) hs[s[i++]] --;

            if(hs == ht) return true;
        }

        return false;
    }
};