438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] sCount = new int[26];
int[] pCount = new int[26];
//初始化窗口
for (int i = 0; i < pLen; ++i) {
++sCount[s.charAt(i) - 'a'];
++pCount[p.charAt(i) - 'a'];
}
//判断初始化窗口是否为 异位词
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
//开始滑动s上的窗口，判断是否为异位词
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(i + 1);
}
}
return ans;
}
}
复杂度分析
时间复杂度：O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。
空间复杂度：O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。
方法二 优化的滑动窗口
differ 来记录当前窗口与字符串 p 中数量不同的字母的个数
滑动窗口
s:source p:target
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] count = new int[26];
1. 初始化滑动窗口
for (int i = 0; i < pLen; ++i) {
++count[s.charAt(i) - 'a'];
--count[p.charAt(i) - 'a'];
}
2. 初始化滑动窗口的differ
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
3. 判断初始化的滑动窗口是否存在异位词
if (differ == 0) {
ans.add(0);
}
4. 开始向右滑动，并进行比较
for (int i = 0; i < sLen - pLen; ++i) {
5. 窗口左边界，之前为1，表示s中比p多1，不同，现在窗口收缩减去，等于0，则differ-1；
之前为0表示相同，现在窗口收缩减去1，等于-1，则differ+1；
--》窗口左边界收缩
if (count[s.charAt(i) - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
--count[s.charAt(i) - 'a'];
6. 窗口右边界，动态更新differ
之前为-1，窗口向右滑动，加1，则等于0，即differ-1
之前为0，现在如果窗口向右滑动，加1，则等于1，即differ+1
==》窗口右边界向右滑动
（判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同）
if (count[s.charAt(i + pLen) - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i + pLen) - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
++count[s.charAt(i + pLen) - 'a'];
if (differ == 0) {
ans.add(i + 1);
}
}
return ans;
}
}
时间复杂度：O(n+m+Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，其中Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要 O(Σ) 来初始化 differ；需要 O(n−m) 来滑动窗口并判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(1) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。
空间复杂度：O(Σ)。用于存储滑动窗口和字符串 p 中每种字母数量的差
