left++; right++; if (patMap.equals(winMap)) { ans.add(left); } }
return ans; }
复杂度分析:
时间复杂度:O(m+(n−m)×Σ),其中 n 为字符串 s 的长度,m 为字符串 p 的长度,Σ 为所有可能的字符数。需要 O(m) 来统计字符串 p 中每种字母的数量;需要 O(m) 来初始化滑动窗口;需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同,每次判断需要 O(Σ)。因为 s 和 p 仅包含小写字母,所以 Σ=26=26。
空间复杂度:O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。
方法二:数组 + 滑动窗口
思路与算法:
方法一中 HashMap 是否相等进行比较太耗时,因为 s 和 p 仅包含小写字母,所以我们只需要使用数组来存储字符串 p 和滑动窗口中每种字母的数量即可。
for (inti=0; i < pLen; i++) { pCnt[p.charAt(i) - 'a']++; wCnt[s.charAt(i) - 'a']++; }
if (check(pCnt, wCnt)) { ans.add(0); }
for (inti=0; i < sLen - pLen; i++) { // minus left wCnt[s.charAt(i) - 'a']--; // plus right wCnt[s.charAt(i + pLen) - 'a']++; if (check(pCnt, wCnt)) { ans.add(i + 1); } }
return ans; }
publicstaticbooleancheck(int[] pCnt, int[] wCnt) { for (inti=0; i < 26; i++) { if (pCnt[i] != wCnt[i]) { returnfalse; } }
returntrue; }
复杂度分析
时间复杂度:O(m+(n−m)×Σ),其中 n 为字符串 s 的长度,m 为字符串 p 的长度,Σ 为所有可能的字符数。需要 O(m) 来统计字符串 p 中每种字母的数量;需要 O(m) 来初始化滑动窗口;需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同,每次判断需要 O(Σ)。因为 s 和 p 仅包含小写字母,所以 Σ=26=26。
public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = newArrayList<>(); intpLen= p.length(); intsLen= s.length(); if (pLen > sLen) { return ans; }
int[] count = newint[26];
for (inti=0; i < pLen; i++) { count[s.charAt(i) - 'a']++; count[p.charAt(i) - 'a']--; }
// different chars intdiff=0; for (int x : count) { if (x != 0) { diff++; } }
if (diff == 0) { ans.add(0); }
for (inti=0; i < sLen - pLen; i++) { charleftCh= s.charAt(i); if (count[leftCh - 'a'] == 1) { diff--; // s has leftCh, p not, diff-- } elseif (count[leftCh - 'a'] == 0) { diff++; // both s and p has leftCh, means move right, will not equal } count[leftCh - 'a']--;
charrightCh= s.charAt(i + pLen); if (count[rightCh - 'a'] == -1) { diff--; // p hash rightCh, s not, that means win will equal } elseif (count[rightCh - 'a'] == 0) { diff++; // both s and p has rightCh, means move right, will not equal } count[rightCh - 'a']++;
if (diff == 0) { ans.add(i + 1); } }
return ans; }
复杂度分析
时间复杂度:O(n+m+Σ),其中 n 为字符串 s 的长度,m为字符串 p 的长度,其中 Σ 为所有可能的字符数。需要 O(Σ) 来初始化 diff;需要 O(n−m) 来滑动窗口并判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同,每次判断需要 O(1)。因为 s 和 p 仅包含小写字母,所以 Σ=26=26。
空间复杂度:O(Σ)。用于存储滑动窗口和字符串 p 中每种字母数量的差。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)