JAVA练习277- 找到字符串中所有字母异位

题目概览给定两个字符串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 * 104s和p仅包含小写字母来源438. 找到字符串中所有字母异位词 - 力扣LeetCode解题分析方法滑动窗口仅包含小写字母可以用数组 mapping 来存储 p 每个字母出现的个数然后定义双指针 i 和 j 都指向 s 第一个字母再定义一个数组 repeatMapping 来存储 i 和 j 中间的所有的字母出现个数每次遍历先判断当前 j 指向字母是否在 mapping 中出现不出现则 i 和 j 都移动到当前位置往右一个位置若出现则再判断在 repeatMapping 中出现个数是否小于 mapping若小于则 j 往右边移动若大于等于则往右移动 i 至当前指向字母相同字母的位置右边并将移动过程所有字母出现个数再 repeatMapping 减去。每次移动判断一下 repeatMapping 是否已经和 mapping 相等相等则记录索引并往右移动一次 i减去 repeatMapping 中 i 原来对应字母个数。时间复杂度O(n m) m 为 p 的长度空间复杂度O(26)class Solution { public ListInteger findAnagrams(String s, String p) { char[] cs s.toCharArray(); int[] mapping new int[26]; for (char c: p.toCharArray()) { mapping[c - a]; } int i 0, j 0; int[] repeatMapping new int[26]; int len 0, pLen p.length(); ListInteger result new ArrayList(); while(i cs.length j cs.length) { if (mapping[cs[j] - a] 0) { if (repeatMapping[cs[j] - a] mapping[cs[j] - a]) { while(repeatMapping[cs[j] - a] mapping[cs[j] - a]) { repeatMapping[cs[i] - a]--; i; len--; } len; repeatMapping[cs[j] - a]; } else { repeatMapping[cs[j] - a]; len; } j; } else { j; i j; len 0; repeatMapping new int[26]; } // System.out.println(String.format(len: %s, i: %d, j: %d, len, i, j)); if (len pLen) { result.add(i); len--; repeatMapping[cs[i] - a]--; i; } } return result; } }