网站标题 没有排名,seo网站沙盒期,网站都需要续费,北京网站空间域名题目描述
因为自己写的复杂度已经到了 O(n)#xff0c;就没有再参考题解的优化了更新#xff1a;滑动窗口方法
思路 代码
用一个 int[ ] count 来存储当前判断子串的各字母出现次数getCount()#xff1a;对当前子串#xff0c;求 count#xff0c;时间复杂度 O(…题目描述
因为自己写的复杂度已经到了 O(n)就没有再参考题解的优化了更新滑动窗口方法
思路 代码
用一个 int[ ] count 来存储当前判断子串的各字母出现次数getCount()对当前子串求 count时间复杂度 O(n)formatString()用 count 转换成当前子串的对比格式时间复杂度 O(1)对比格式如abcccz 变成 “a1b1c3z1”实际上getCount只要使用两次即可一次给 p一次给 s 的第一个子串往后s 的字串只需要对之前的 count 进行微小更新即可
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ans new ArrayList();int pLen p.length();if(s.length() pLen){return ans;}char[] sC s.toCharArray();char[] pC p.toCharArray();// p的formatint[] count new int[26];getCount(pC, count);String formatP formatString(count);// s的初始countcount new int[26];getCount(s.substring(0, pLen).toCharArray(), count);// 0的处理String formatQ formatString(count);if(formatQ.equals(formatP)){ans.add(0);}// 从1开始for(int i 1; i pLen s.length(); i){char last sC[i pLen - 1];char pre sC[i - 1];if(last ! pre){count[last - a];count[pre - a]--;formatQ formatString(count); }if(formatQ.equals(formatP)){ans.add(i);}}return ans;}// 函数时间复杂度O(n)void getCount(char[] now, int[] count){for(char ch : now){count[ch - a];}}String formatString(int[] count){StringBuilder formatNow new StringBuilder();for(int i 0; i 26; i){if(count[i] ! 0){formatNow.append((char)(i a));formatNow.append(count[i]);}}return formatNow.toString();}
}更新版
现在看之前的代码简直不堪入目…好长好冗余新思路等大滑动窗口数组维护滑动窗口值Arrays.equals() 用作对比
class Solution {public ListInteger findAnagrams(String s, String p) {if(s.length() p.length()) {return new ArrayList();}int[] sCounts new int[26];int[] pCounts new int[26];ListInteger ans new ArrayList();for(int i 0; i p.length(); i) {sCounts[s.charAt(i) - a];pCounts[p.charAt(i) - a];}if(Arrays.equals(sCounts, pCounts)) {ans.add(0);}int left 0, right p.length() - 1;while(right s.length() - 1) {sCounts[s.charAt(left) - a]--;sCounts[s.charAt(right) - a];if(Arrays.equals(sCounts, pCounts)) {ans.add(left);}}return ans;}
}三刷 - 每日一题
滑动窗口20行以内解决
class Solution {public ListInteger findAnagrams(String s, String p) {if(s.length() p.length()) return new ArrayList();ListInteger ans new ArrayList();int[] sCounts new int[26];int[] pCounts new int[26];for(int i 0; i p.length(); i) {sCounts[s.charAt(i) - a];pCounts[p.charAt(i) - a];}if(Arrays.equals(sCounts, pCounts)) ans.add(0);int left 0, right p.length() - 1;while(right s.length() - 1) {sCounts[s.charAt(left) - a]--;sCounts[s.charAt(right) - a];if(Arrays.equals(sCounts, pCounts)) ans.add(left);}return ans;}
}
