【滑动窗口】找到字符串中所有字⺟异位词（medium）

题⽬链接：438. 找到字符串中所有字⺟异位词

题⽬描述：

给定两个字符串 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” 的异位词。
提⽰:
1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含⼩写字⺟

解法（滑动窗⼝ + 哈希表）：

算法思路：

◦ 因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构
造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；
◦ 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p
的异位词；
◦ 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个
数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。

C++ 算法代码：

class Solution{
public:vector<int> findAnagrams(string s, string p){vector<int> ret;int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数for(auto ch : p) hash1[ch - 'a']++;int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数int m = p.size();for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];// 进窗⼝ + 维护 countif(++hash2[in - 'a'] <= hash1[in - 'a']) count++; if(right - left + 1 > m){ // 判断char out = s[left++];// 出窗⼝ + 维护 countif(hash2[out - 'a']-- <= hash1[out - 'a']) count--; }// 更新结果if(count == m) ret.push_back(left);}return ret;}
}

Java 算法代码：

class Solution{public List<Integer> findAnagrams(String ss, String pp){List<Integer> ret = new ArrayList<Integer>();char[] s = ss.toCharArray();char[] p = pp.toCharArray();int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数for(char ch : p) hash1[ch - 'a']++;int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数int m = p.length;for(int left = 0, right = 0, count = 0; right < s.length; right++){char in = s[right];// 进窗⼝ + 维护 countif(++hash2[in - 'a'] <= hash1[in - 'a']) count++; if(right - left + 1 > m){ // 判断char out = s[left++];// 出窗⼝ + 维护 countif(hash2[out - 'a']-- <= hash1[out - 'a']) count--; }// 更新结果if(count == m) ret.add(left);}return ret;}
}

注：

if(right-left+1>m){if(hash2[ss[left++]-'a']--<=hash1[ss[left++]-'a']){count--;} 
}

是错的

可改为·

if(right-left+1>m){char leftChar = ss[left++];if(hash2[leftChar-'a']--<=hash1[leftChar-'a']){count--;} 
}

或

if(right-left+1>m){if (hash2[ss[left] - 'a']-- <= hash1[ss[left] - 'a']) count--;left++;
}