网站的功能,便宜的seo官网优化,镇江本地网,安康市移动公司电话给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;。
示例 1:
输入: s “cbaebabacd”, p “abc” 输出:…给定两个字符串 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 * 104
s 和 p 仅包含小写字母1.滑动窗口,出现频率
思路
字符串 sss 中构造一个长度为与字符串 p 的长度相同的滑动窗口构建字母出现的频率表比较出现频率
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ans new ArrayListInteger();int sLen s.length(), pLen p.length();if(s null || p null || sLen pLen) {return ans;}// 构建字母出现的频率表int[] sCount new int[26];int[] pCount new int[26];//第一次for (int i 0; ipLen; i) {sCount[s.charAt(i) - a];pCount[p.charAt(i) - a];}if(Arrays.equals(sCount, pCount)) {ans.add(0);}for (int i 0; i sLen - pLen; i) {// 左侧将要划出减去一次sCount[s.charAt(i) - a]--;// 右侧滑入增加一次sCount[s.charAt(i pLen) - a];// 再次比较频率表if(Arrays.equals(sCount, pCount)) {ans.add(i1);}}return ans;}
}执行用时分布 8ms 击败71.71%使用 Java 的用户 消耗内存分布 43.79MB 击败37.70%使用 Java 的用户
2.滑动窗口,反向思维
class Solution {public ListInteger findAnagrams(String s, String p) {ArrayListInteger ans new ArrayList();if (s.length() p.length()) return ans;int[] counts new int[26]; // 欠账表欠的字符 - 欠的个数int all p.length(); // 总欠账数目// 统计欠账生成欠账表:for (char c : p.toCharArray()) counts[c-a];// 【滑动窗口】还账int l 0, r 0, n s.length();char[] str s.toCharArray();for (; l n; l) {// 窗口右边界字符进入窗口还账如果不超额还账就一直还while (r n counts[str[r] - a] 0) {all--;counts[str[r] - a]--;}// 还账结束看当前窗口内是否还清了所有欠账if (all 0) ans.add(l);// 窗口左边界字符出窗口重新赊账counts[str[l] - a];all;}return ans;}
}执行用时分布 3ms 击败99.94%使用 Java 的用户 消耗内存分布 43.63MB 击败47.83%使用 Java 的用户
