LeetCode

1.题目2.思路3.代码实现（Java)

给你两个字符串 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 <= 10⁴
s1 和 s2 仅包含小写字母

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

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

//思路1————滑动窗口
public boolean checkInclusion(String s1, String s2) {
    int s1Len = s1.length();
    int s2Len = s2.length();
    //res用于保存结果
    boolean res = false;
    HashMap window = new HashMap();
    HashMap need = new HashMap();
    
    //将字符串s1中的字符存入哈希表need中，key/value为字符/出现的次数
    for(int i=0;i= 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;
}