題目描述

• 因?yàn)樽约簩懙膹?fù)雜度已經(jīng)到了 O(n)，就沒有再參考題解的優(yōu)化了
• 更新：滑動(dòng)窗口方法
  

思路 & 代碼

• 用一個(gè) int[ ] count 來存儲(chǔ)當(dāng)前判斷子串的各字母出現(xiàn)次數(shù)
• getCount()：對(duì)當(dāng)前子串，求 count，時(shí)間復(fù)雜度 O(n)
• formatString()：用 count 轉(zhuǎn)換成當(dāng)前子串的對(duì)比格式，時(shí)間復(fù)雜度 O(1)
• 對(duì)比格式：如"abcccz" 變成 “a1b1c3z1”
• 實(shí)際上，getCount只要使用兩次即可：一次給 p，一次給 s 的第一個(gè)子串
• 往后，s 的字串只需要對(duì)之前的 count 進(jìn)行微小更新即可

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> 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;}// 函數(shù)時(shí)間復(fù)雜度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();} }

更新版

• 現(xiàn)在看之前的代碼簡直不堪入目…好長好冗余
• 新思路：等大滑動(dòng)窗口，數(shù)組維護(hù)滑動(dòng)窗口值，Arrays.equals() 用作對(duì)比

class Solution {public List<Integer> findAnagrams(String s, String p) {if(s.length() < p.length()) {return new ArrayList<>();}int[] sCounts = new int[26];int[] pCounts = new int[26];List<Integer> 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;} }

三刷 - 每日一題

• 滑動(dòng)窗口，20行以內(nèi)解決～

class Solution {public List<Integer> findAnagrams(String s, String p) {if(s.length() < p.length()) return new ArrayList<>();List<Integer> 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;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】438. 找到字符串中所有字母异位词（Java、字符串、滑动窗口）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。