【leetcode】438 找到字符串中所有异位词（滑动窗口，双指针，哈希表）

题目链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

题目描述

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。

不考虑答案输出的顺序。

示例 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" 的字母异位词。
           

思路

使用滑动窗口-双指针方法。一次遍历。

复杂度分析

• 时间复杂度：O（n）
• 空间复杂度：O（1）

注意：从该题的标准输出发现其实不需要排除与p相同的排列；所以只要字符的分布与p相同即可

代码

/*
 * 滑动窗口-双指针
 */
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        if(p.size() > s.size()) return ret;
        unordered_map<char, int> need;
        unordered_map<char, int> window;
        for(char c:p)        // 统计p的字符分布
            need[c] ++;
        int left = 0, right = 0;
        int match = 0;       // 匹配的字符数
        while (right < s.size()){
            char c1 = s[right];
            if(need.count(c1)){
                window[c1] ++;
                if(window[c1] == need[c1])
                    match ++;
            }
            right ++;

            while (match == need.size()){
                if(right - left == p.size())
                    ret.push_back(left);

                char c2 = s[left];
                if(need.count(c2)){
                    window[c2] --;
                    if(window[c2] < need[c2])
                        match--;
                }
                left++;
            }
        }

        return ret;
    }
};