给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 10^4s和p仅包含小写字母
1 class Solution { 2 public List<Integer> findAnagrams(String s, String p) { 3 HashMap<Character, Integer> window = new HashMap<>(); 4 HashMap<Character, Integer> need = new HashMap<>(); 5 for (char c : p.toCharArray()) { 6 need.put(c, need.getOrDefault(c, 0) + 1); 7 } 8 int left = 0, right = 0; 9 int valid = 0; 10 int sLen = s.length(); 11 int pLen = p.length(); 12 List<Integer> res = new ArrayList<>(); 13 while (right < sLen) { 14 char c = s.charAt(right); 15 //窗口左闭右开,[left, right) 16 right++; 17 if (need.containsKey(c)) { 18 window.put(c, window.getOrDefault(c, 0) + 1); 19 if (window.get(c).equals(need.get(c))) { 20 valid++; 21 } 22 } 23 if (right - left == pLen) { 24 if (valid == need.size()) { 25 res.add(left); 26 } 27 char d = s.charAt(left); 28 left++; 29 if (need.containsKey(d)) { 30 if (window.get(d).equals(need.get(d))) { 31 valid--; 32 } 33 window.put(d, window.get(d) - 1); 34 } 35 } 36 } 37 return res; 38 } 39 }