网站更换服务器要重新备案吗,网站忘了怎么办啊,毕业了智慧团建密码忘了,番禺人才网最新招聘市场在哪里?给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 示例 1: 输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cba, 它是 a… 给定两个字符串 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 ListInteger findAnagrams(String s, String p) {char[] chars p.toCharArray();Arrays.sort(chars); //排序完的字符串数组//创建对象String sorted new String(chars);//键:p字符串 值:异位词下标HashMapString, ListInteger map new HashMap();map.put(sorted, new LinkedListInteger());//遍历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);}}}ListInteger result map.get(sorted);return result;}
/*** 哈希表 滑动窗口* abab ab*/public ListInteger findAnagrams2(String s, String p) {ListInteger 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 宫水三叶
