438. Find All Anagrams in a String 发表于 2021-12-15 1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> startIndexList = new ArrayList<>(); if (p.length() > s.length()) { return startIndexList; } int[] targetCountMap = new int[26]; int targetDistinctCharCount = 0; for (int i = 0; i < p.length(); i++) { if (targetCountMap[p.charAt(i) - 'a']++ == 0) { targetDistinctCharCount++; } } int[] windowCountMap = new int[26]; int distinctCharCount = 0; int i = 0; for (int j = 0; j < s.length(); j++) { int offset = s.charAt(j) - 'a'; if (++windowCountMap[offset] == targetCountMap[offset]) { distinctCharCount++; } while (distinctCharCount == targetDistinctCharCount) { // 当不同的字符数已经匹配时,说明窗口字符串长度大于等于目标字符串长度,此时检查字符串长度是否相同 if (j - i + 1 == p.length()) { startIndexList.add(i); } // 尝试缩小窗口 int leftmostOffset = s.charAt(i++) - 'a'; if (windowCountMap[leftmostOffset]-- == targetCountMap[leftmostOffset]) { distinctCharCount--; } } } return startIndexList; }} Reference438. Find All Anagrams in a String剑指 Offer II 015. 字符串中的所有变位词