力扣.找到打字符串中所有字母异位词

给定两个字符串 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" 的异位词。

思路

        一但遇到要在一个串中找另一个串的子串，90%都可以用到滑动窗口的方法，

滑动窗口算法的思路是这样：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这题不光要用到滑动窗口，因为还出现了异位词，所以还需要用到哈希表来解决出现的异位问题

unordered_map 就是哈希表（字典），count是它的一个方法用来查看对应key是否在表中  

可以使用方括号访问键对应的值 map[key]。需要注意的是，如果该 key 不存在，C++ 会自动创建这个 key，并把 map[key] 赋值为 0。

代码如下：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int l = 0, r = 0;     // 定义左右指针[l,righr)
        int cnt = 0;          // 用来统计已找到的字符种类数（ps：如果A有2个，只找到1个 cnt不加，全找齐才算）
        vector<int> res;      // 用来接收最后返回的结果
        unordered_map<char, int> need,window; //定义两个哈希表
        for (auto e : p){    // 记录下需要找的字符的hash值
            need[e]++;
                 
        while (r < s.size()){
            // 更新滑动窗口右端，并记录窗口内的hash值与cnt，然后右移
            char c = s[r];
            if (need.count(c)){  // 说明新进入窗口的字符是我们要找的
                window[c]++;     // 先更新字符的窗口hash表     
                if (window[c] == need[c]) cnt++;    // 判断该类字符是否全部找齐,若找齐cnt+1                 
            } 
            r++;                                    //若不是要找的或记录完后指针右移

            // 判断左侧指针时候需要移动:窗口内的元素(r-l+1)大于p串的大小时需要移动
            while (r-l+1 > p.size()){    
                if (cnt == need.size()){            // 当窗口符合条件时，把起始索引加入 res
                    res.push_back(l);
                }

                // 判断是否需要更新移动当前left后变化的window哈希表（不要忘记cnt）
                char d = s[l];
                if (need.count(d)){
                    if (window[d] == need[d]) cnt--;// 判断条件必须写，因为存在找到了但没找全的情况，所以移动指针cnt也不会减                          
                    window[d]--;                    // 该项必须放在if判断的后面，因为window[d]的值改变对判断有影响
                }

                l++;                                //该位置如果不是需要的或是已做完处理后移动指针
            }
        }   
        return res;
    }        
};

相关题目：

1.字母异位词分组

2.有效的字母异位词