1
2
3

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

1
2

输入：s1= "ab" s2 = "eidboaoo"
输出：false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
public:
    /**
    ## 解题思路
    * 双指针法+滑动窗口
    1. 先用一个hash_map统计s1中各个字符出现的频次；
    2. 再遍历s2,；
    3. 使用l,r建立滑动窗口，表示滑动窗口的左右边界；
    4. 遍历时，判断窗口内各字符和hash_map中各个字符的频次；
    5. 使用一个变量count记录当前窗口内和s1中各字符频次不同的字符个数；
    **/
    bool checkInclusion(string s1, string s2) {
        //使用hash_map统计s1中各字符出现的频次
        unordered_map<char, int> sc; 
        for(auto s: s1) {
            sc[s]++;
        }
        int k = s1.length();  
        int l2 = s2.length();
        int l=0, r=0;   //滑窗左右指针 
        int count=sc.size();    //窗口中字符频次与s1不等的字符个数
        char c, c2;
        //
        while(r<l2) {
            c = s2[r];      //处理右边界字符
            //当前字符在map中，减少map[c]的频次；
            if(sc.find(c)!=sc.end()) {
                if(--sc[c] == 0) { //当前字符和hash_map中的字符频次相等;
                    count--;       //不等频次计数-1；
                }
            }
            
            if(r-l+1<k) {  //如果窗口大小小于s1长度，
                r++;       //则扩展窗口右边界(直到滑窗长度和s1相等)；
            } else if(r-l+1 == k) { //窗口大小刚好和s1大小相等
                if(count==0) {      //窗口中的所有字符和s1中的频次相同，count为0
                    return true;
                }
                // 右滑窗口，滑出左边界字符
                // 如果左边界字符在s1中
                c2 = s2[l];
                if(sc.find(c2) != sc.end()) {   //如果左边字符在s1中
                    sc[c2]++;         //还原该字符的频次
                    if(sc[c2]++ == 1) {           //如果该字符是最后一个，由于下一步要移动左边界l
                        count++;                //则说明当前窗口和s1中频次相等的字符数个数少了一个
                    }                           //因此count+1；
                }
                //窗口向右滑动一格
                l++; 
                r++;                            
            }
        }

        return false;
    }
};