567. 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False滑动窗口问题，使用两个HashMap，needed保存s1中字母个数的信息，window就表示我们的滑动窗口，再定义一个int的matched表示匹配了多少个字母，遍历s2将字符更新进window中，若该字符在window中的个数等于needed中该字符的个数，那么就表示这个字符已经匹配了，matched++，每遍历s2中的一个字符，就比较matched与needed.size()是否相等，相等，则判断窗口的长度是否等于s1.length，是的话就说明找到了返回true。
public boolean checkInclusion(String s1, String s2) { Map<Character,Integer> needed = new HashMap<>(); Map<Character,Integer> window = new HashMap<>(); for (int i = 0;i<s1.length();i++){ char c = s1.charAt(i); needed.put(c, needed.getOrDefault(c, 0)+1); } int l=0,r=0; //[l,r) int matched = 0; while (r<s2.length()){ Character c = s2.charAt(r); if (needed.containsKey(c)){ window.put(c, window.getOrDefault(c, 0)+1); if (needed.get(c).equals(window.get(c))){ matched++; } } r++; while (matched==needed.size()){ if (r-l==s1.length()){ return true; } Character c1 = s2.charAt(l); if (needed.containsKey(c1)){ window.put(c1, window.get(c1)-1); if (window.get(c1).compareTo(needed.get(c1))<0){ matched--; } } l++; } } return false; }