LeetCode_438.找到字符串中所有字母异位词
给定两个字符串
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仅包含小写字母
时间复杂度太大 md
public List<Integer> findAnagrams(String s, String p) {char[] chars = p.toCharArray();Arrays.sort(chars); //排序完的字符串数组//创建对象String sorted = new String(chars);//键:p字符串 值:异位词下标HashMap<String, List<Integer>> map = new HashMap<>();map.put(sorted, new LinkedList<Integer>());//遍历s字符串for (int left = 0; left < s.length(); left++) {int right = left + p.length();if (right <= s.length()) {//截取s字符串的p.length()个单位String substring = s.substring(left, right);char[] chars2 = substring.toCharArray();Arrays.sort(chars2); //排序完的字符串数组String sorted2 = new String(chars2);//判断 sorted sorted2 是否一致 因为按照重排的计算if (Objects.equals(sorted2, sorted)) {map.get(sorted).add(left);}}}List<Integer> result = map.get(sorted);return result;}/*** 哈希表 + 滑动窗口* abab ab*/public List<Integer> findAnagrams2(String s, String p) {List<Integer> ans = new ArrayList<>();int n = s.length(), m = p.length(); //m = 2/*** 我们可以先创建一个大小为 26 的数组 c2 来统计字符串 p 的词频，* 另外一个同等大小的数组 c1 用来统计「滑动窗口」内的 s 的子串词频* 当两个数组所统计词频相等，说明找到了一个异位组，将窗口的左端点加入答案。*/int[] c1 = new int[26], c2 = new int[26];//更新c2的哈希表for (int i = 0; i < m; i++) c2[p.charAt(i) - 'a']++;for (int left = 0, right = 0; right < n; right++) {//c1[s.charAt(right) - 'a']++;//双指针if (right - left + 1 > m) c1[s.charAt(left++) - 'a']--;if (check(c1, c2)) ans.add(left);}return ans;}boolean check(int[] c1, int[] c2) {for (int i = 0; i < 26; i++) {if (c1[i] != c2[i]) return false;}return true;}//来源:leetcode 宫水三叶