给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

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

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

• 输入的字符串只包含小写字母
• 两个字符串的长度都在 [1, 10,000] 之间

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思想

滑动窗口

• 先将s1每个字符的个数存到map中，再定义一个临时map存放滑动窗口中每一个字符的个数以及一个整型变量存放和s1中字符的个数匹配的字符个数
• 如果当前字符不在s1中，左右指针都指向当前字符的下一个，同时要清空下临时map以及匹配的个数
• 如果当前字符在s1中，右指针移动，并判断左右指针区域内的子串是否是s1的排列，如果当前字符的个数等于s1中该字符的个数，匹配的个数+1，如果大于，就需要循环移动左指针，直到不大于为止

class Solution {
public:bool checkInclusion(string s1, string s2) {unordered_map<char, int> mt;for(auto a : s1)++mt[a];unordered_map<char, int> temp;int l = 0, r = 0;int cnt = 0;//用来统计滑动窗口中已经有几个字符达到了s1中的个数while(r < s2.size()){if(mt.count(s2[r])){temp[s2[r]]++;if(temp[s2[r]] == mt[s2[r]])++cnt;while(l <= r && temp[s2[r]] > mt[s2[r]]){if(temp[s2[l]] == mt[s2[l]])--cnt;temp[s2[l]]--;++l;}if(cnt == mt.size())return true;++r;}else{cnt = 0;temp.clear();++r;l = r;}}return false;}
};