438. 找到字符串中所有字母异位词（LeetCode 热题 100）

题目来源：

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

---

题目内容：

给定两个字符串 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 * 104

• s 和 p 仅包含小写字母

---

思路分析：

• 思路一：不定长滑窗   来源:灵茶山艾府

  枚举子串s′的右端点，如果发现s′其中一种字母的出现次数大于 p的这种字母的出现次数，则右移s′的左端点。如果发现s′的长度等于p的长度，则说明s′的每种字母的出现次数，和p的每种字母的出现次数都相同，那么s′是p的异位词。

---

代码实现（版本一：灵神（附带注释））：

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;int cnt[26];//记录p中每种字母出现的次数，，这里我觉得也可以使用哈希表实现for(char c:p) cnt[c-'a']++;int left =0;for(int right=0;right<s.size();right++){int  c=s[right]-'a';cnt[c]--;while(cnt[c]<0){//是循环  字母c太多了cnt[s[left]-'a']++;//左端点向后移动left++;}if(right-left+1==p.length()){//经过上面while循环s‘和p的每种字符出现次数都相同ans.push_back(left);}}return ans;}
};

代码实现（版本二：int数组ant 替换成哈希表）：

我再想想

---

题目心得：

1. 体会题目解法的精妙思想：
   滑动窗口是怎么实现的？/为什么要用滑动窗口？

2. 比较滑动窗口和双指针算法的区别

3. int/char  c=s[right]-'a';  //这里的c两种类型都可以运行

4. 最近在读一本书《刻意练习》
   作者在通过举例的方式想向我们传达一种思想：

• 一些国际象棋大师，之所以厉害是因为，他们的脑袋里存储了上万个残局模型，在比赛/下棋过程中，针对不通的情况，进行调用/做出改善。

• 我觉得我们学习算法的过程亦是如此，先针对基础的算法进行学习，在头脑中积累算法模板，最后遇到题目/实际问题，进行合适的调用并输出。

• 说了这么多。就是想表达。有时候不用太纠结。不会了就看看答案（但一定要自己敲一遍）。多记忆一些。下次才会有思路。