1.题目

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).

示例 2：
输入：s1= “ab” s2 = “eidboaoo”
输出：false

提示：
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string

2.思路

（1）滑动窗口
此题与LeetCode_滑动窗口_困难_76.最小覆盖子串类似，只不过找到一个合法子串之后，可以直接返回true，如果遍历结束后仍未找到，则返回false。

3.代码实现（Java)

//思路1————滑动窗口
public boolean checkInclusion(String s1, String s2) {
    int s1Len = s1.length();
    int s2Len = s2.length();
    //res用于保存结果
    boolean res = false;
    HashMap<Character, Integer> window = new HashMap<Character, Integer>();
    HashMap<Character, Integer> need = new HashMap<Character, Integer>();
    
    //将字符串s1中的字符存入哈希表need中，key/value为字符/出现的次数
    for(int i=0;i<s1Len;i++){
        char c = s1.charAt(i);
        need.put(c, need.getOrDefault(c,0) + 1);
    }
    
    int left = 0,right = 0;
    //valid记录窗口中s1中字符的种类数
    int valid = 0;
    while(right < s2Len){
        char c = s2.charAt(right);
        right++;
        //更新窗口内的数据
        if(need.containsKey(c)){
            window.put(c,window.getOrDefault(c,0)+1);
            //s2中的字符c已经全部加入到window中
            if(window.get(c).equals(need.get(c))){
                valid++;
            }
        }
        //判断左侧窗口是否要收缩
        while(right - left >= s1Len){
            //找到了合法的子串，则直接返回true
            if(valid == need.size()){
                return true;
            }
            //d是即将移出窗口的字符
            char d = s2.charAt(left);
            left++;
            //更新窗口内的数据
            if(need.containsKey(d)){
                if(window.get(d).equals(need.get(d))){
                    valid--;
                }
                window.put(d,window.get(d)-1);
            }
        }
    }
    return res;
}