题目
给定两个字符串 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" 的异位词。
解题
方法一：定长滑动窗口（暴力）
一个和p一样长度的滑动窗口，然后用vector作为哈希，记录每个元素出现的次数，然后比较vector相等就行了，比较暴力的解法。
class Solution { public: bool isValid(vector<int>& a,vector<int>& b){ for(int i=0;i<26;i++){ if(a[i]!=b[i]) return false; } return true; } vector<int> findAnagrams(string s, string p) { int n=p.size(); vector<int> hash(26,0),cur(26,0); for(char c:p){ hash[c-'a']++; } vector<int> res; for(int i=0;i<s.size();i++){ if(i>=n){ cur[s[i-n]-'a']--; } cur[s[i]-'a']++; if(i>=n-1&&isValid(hash,cur)){ res.push_back(i-n+1); } } return res; } };
方法二：变长滑动窗口
class Solution { public: vector<int> findAnagrams(string s, string p) { int n=p.size(); vector<int> hash(26,0),cur(26,0); for(char c:p){ hash[c-'a']++; } vector<int> res; int left=0; for(int right=0;right<s.size();right++){ int idx=s[right]-'a'; cur[idx]++; while(cur[idx]>hash[idx]){//如果新加了字符后，使得该字符数量多于p的，那么滑动窗口左边界开始向右滑动 cur[s[left]-'a']--; left++; } if(right-left+1>=n){//滑动窗口的大小为n就说明符合异位词的条件 res.push_back(right-n+1); } } return res; } };
