题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

题目分析

1. 在字符串 s中使用同向双指针来查询p的异位词，并在移动左右指针时维护左右指针间每种字母的数量；
2. 先统计p中各字符的数量到一个数组（模拟哈希表）中；
3. 每次移动右指针时，数组中对应的元素数量减一；相反，移动左侧指针时，需要将对应的元素数量加一；
4. 当右指针指向的字母的数量小于0时，则移动左指针；
5. 当窗口中每种字母的数量与字符串 p中每种字母的数量相同时，则说明当前窗口为字符串 p的异位词；

Code

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> res;int cnt[26] = {0};for (int i=0; i< p.size(); ++i) {cnt[p[i] - 'a']++;}int left=0;for (int right=0; right<s.size(); ++right) {cnt[s[right] - 'a']--;while (cnt[s[right] - 'a'] < 0) {cnt[s[left] - 'a']++;left++;}if (right - left + 1 == p.size()) {res.emplace_back(left);}}return res;}
};