石家庄专业制作网站,军事新闻俄乌最新消息,无锡科技网站建设,合肥网络推广技巧一、题目 给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;。 示例 1:
输入: s cbaebabacd, … 一、题目 给定两个字符串 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 的异位词。 二、思路解析 这道题的关键在于想到利用一个 变量 count 来记录窗口中的 「有效字符」 个数。
而有效数字存在的前提就是 s 中每一个字符的出现次数一定不能超过 p 中对应符的出现次数否则就不是题目要求的子串了。
这道题我用了 2 个数组来记录 s 和 p 中每个字符的出现次数其中数组下标为字符的 ACII 码值。
剩下的就是滑动窗口的实现跟维护、 count 的维护以及结果的更新了具体步骤我也有在下面代码注释中写到啦。 三、完整代码 class Solution {public ListInteger findAnagrams(String ss, String pp) {char[] s ss.toCharArray();char[] p pp.toCharArray();int n s.length;int m p.length;ListInteger ret new ArrayListInteger();//记录 p 中每个字符的出现次数其中数组下标为字符的 ACII 码值int[] hash1 new int [26];for(char ch : p){hash1[ch - a];}//滑动窗口int[] hash2 new int [26];for(int left 0 , right 0 , count 0; right n ; right ){char in s[right];//count 用于记录有效字符「即 s 字符串中的 a 字符数量 p 字符串中的 a 字符数量」if(hash2[in - a] hash1[in - a]){count ;}//进入窗口 维护 countif(right - left 1 m){char out s[left];if(hash2[out - a]-- hash1[out - a] ){count --;}}//出窗口 维护 count//更新结果if(count m){ret.add(left);}}return ret;}
} 以上就是本篇博客的全部内容啦如有不足之处还请各位指出期待能和各位一起进步
