滑动窗口（二）

滑动窗口（二）这个专题是滑动窗口结合哈希表，通常哈希表的作用是判断一个字符或者字符串是否在另一个中出现过。?

滑动窗口中的判断条件的逻辑通常需要自己来想，不能一概而论。

多画图，搞清楚到底是如何从暴力解法转化成更优秀的滑动窗口解法才最重要！

水果成篮

水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组?fruits?表示，其中?fruits[i]?是第?i?棵树上的水果?种类?。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有?两个?篮子，并且每个篮子只能装?单一类型?的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从?每棵?树（包括开始采摘的树）上?恰好摘一个水果?。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组?fruits?，返回你可以收集的水果的?最大?数目。

思路：使用哈希表对水果的种类进统计，利用滑动窗口算法来解决问题。

题目中给出的 “?fruits[i]?是第?i?棵树上的水果?种类 ”得意思是树上的水果种类是 0，1，2 这些，而不是树上有几种水果，一棵树上只能有一种水果！

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> hash;// 统计窗口中出现了哪些水果，并且他们出现的个数
        int ret = 0, left = 0, right = 0, n = fruits.size();
        while(right < n)
        {
            hash[fruits[right]]++;
            while(hash.size()>2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0) hash.erase(fruits[left]);
                left++;
            }
            ret = max(ret, right - left + 1);
            right ++;
        }
        return ret;
    }
};

由于题目中给出了数据范围，所以可以使用数组直接充当哈希表来提高效率！

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //数据范围为 0 ~ 100000,可以用数组来模拟哈希表
        int hash[100001] = { 0 };
        int left = 0, right = 0, kinds = 0,n = fruits.size();// kinds用来维护哈希表里的水果种类
        int ret = 0;
        while(right < n)
        {
            if(hash[fruits[right]] == 0) kinds++;
            hash[fruits[right]]++;
            while(kinds > 2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) kinds--;
                left++;
            }
            right++;
            ret = max(ret,right - left);
        }
        return ret;
    }
};

找到字符串中所有字母异位词

找到字符串中所有字母异位词

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

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

思路：将 p 中的字符放入 hash2 ，利用滑动从窗口和哈希表在 s 中，当 hash1 等于 hash2 的时候，就是一个符合题目题目要求的条件，这时候就要更新结果，并使窗口继续滑动。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n1 = s.size(), n2 = p.size();
        int left = 0, right = 0, len = n2;
        unordered_map<int, int> hash1,hash2;
        vector<int> v;
        while (len)
        {
            hash2[p[--len]]++;
            hash1[s[right++]]++;
        }
        while (right < n1)
        {
            while (right < n1 && hash1 == hash2)
            {
                v.push_back(left);
                hash1[s[right++]]++;
                hash1[s[left]]--;
                if (hash1[s[left]] == 0) hash1.erase(s[left]);
                left++;
            }
            if (right < n1)
            {
                hash1[s[right++]]++;
                hash1[s[left]]--;
                if (hash1[s[left]] == 0) hash1.erase(s[left]);
                left++;
            }              
        }
        if (hash1 == hash2) v.push_back(left);
        return v;
    }
};

串联所有单词的子串?

串联所有单词的子串

?给定一个字符串?s?和一个字符串数组?words。?words?中所有字符串?长度相同。

?s?中的?串联子串?是指一个包含??words?中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果?words = ["ab","cd","ef"]， 那么?"abcdef"，?"abefcd"，"cdabef"，?"cdefab"，"efabcd"， 和?"efcdab"?都是串联子串。?"acdbef"?不是串联子串，因为他不是任何?words?排列的连接。

返回所有串联子串在?s?中的开始索引。你可以以?任意顺序?返回答案。

这道题目，是上一道题目的升级版，并且只能采用哈希表的容器来解决这道题目，相当于这道题是每次指针向前走 words 里的字符串长度个距离，然后在进行这个长度次循环，就能遍历出所有结果！

细节就是如果哈希表定义在外面，每进行一次循环就要清空一次哈希表！当然更好的情况是将哈希表直接定义在循环里。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> v1;
        unordered_map<string, int> hash1;
        unordered_map<string, int> hash2;
        //先将 vector 里的字符串放入哈希表
        int n = s.size(), len = words[0].size(), count = words.size();
        //先将 vector 里的字符串放入哈希表
        for (int i = 0; i < count; i++) hash2[words[i]]++;
        for (int i = 0; i < len; i++)
        {
            int left = i, right = i;
            while (right < n)
            {
                hash1[s.substr(right, len)]++; 
                if (hash1 == hash2)
                {
                    v1.push_back(left);
                }
                if (right - left >= (count - 1) * len)
                {
                    hash1[s.substr(left, len)]--;
                    if(hash1[s.substr(left,len)]==0) hash1.erase(s.substr(left, len));
                    left += len;
                }
                right += len;
            }
            hash1.clear();
        }
        return v1;
    }
};

最小覆盖子串

最小覆盖子串

给你一个字符串?s?、一个字符串?t?。返回?s?中涵盖?t?所有字符的最小子串。如果?s?中不存在涵盖?t?所有字符的子串，则返回空字符串?""?。

注意：

• 对于?t?中重复字符，我们寻找的子字符串中该字符数量必须不少于?t?中该字符数量。
• 如果?s?中存在这样的子串，我们保证它是唯一的答案

思路：利用哈希表，采用滑动窗口解题，其中 count 记录的是目标哈希表中字符的种类数。?

更新 count 的条件：在进窗口后和出窗口前判断进来的和即将要出去的字符，是否等于 hash2 中对应字符的个数，只有等于才能更新结果（count-- 和 count++，hash1 中字符的个数）

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash2;
        unordered_map<char, int> hash1;
        int len = t.size(), left = 0, right = 0, n = s.size();
        for (int i = 0; i < len; i++) hash2[t[i]]++;
        int minlen = INT_MAX;
        int flag = 0,begin=-1;
        int count = 0;//统计窗口中有效字符的种类
        while (right < n)
        {
            hash1[s[right]]++;
            //判断是否让有效字符种类++
            if (hash2.count(s[right]) > 0 && hash1[s[right]] == hash2[s[right]]) count++;
            while (count == hash2.size())
            {
                flag = 1;
                if (right - left + 1 < minlen) 
                {
                    minlen = right -left +1;
                    begin = left;
                }
                if ((hash2.count(s[left]) > 0 )&& hash1[s[left]] == hash2[s[left]]) count--;
                hash1[s[left++]]--;
            }
            right++;
        }
        if(begin == -1) return "";
        else return s.substr(begin,minlen);
    }
};

?

依然是这个思路，因为字符全是字母，所以可以采用大小为128的数组来代替哈希表，这样时间复杂度可以大大提升，只需要对细节进行处理即可。

class Solution {
public:
    string minWindow(string s, string t) {
        int hash2[128] = {0};
        int hash1[128] = {0};
        int len = t.size(), left = 0, right = 0, n = s.size();
        int kinds = 0;
        for (int i = 0; i < len; i++) 
        {
            if(hash2[t[i]] == 0) kinds++;
            hash2[t[i]]++;
        }
        int minlen = INT_MAX;
        int flag = 0,begin=-1;
        int count = 0;//统计窗口中有效字符的种类
        while (right < n)
        {
            hash1[s[right]]++;
            //判断是否让有效字符种类++
            if (hash2[s[right]] > 0 && hash1[s[right]] == hash2[s[right]]) count++;
            while (count == kinds)
            {
                flag = 1;
                if (right - left + 1 < minlen) 
                {
                    minlen = right -left +1;
                    begin = left;
                }
                if ((hash2[s[left]] > 0 )&& hash1[s[left]] == hash2[s[left]]) count--;
                hash1[s[left++]]--;
            }
            right++;
        }
        if(begin == -1) return "";
        else return s.substr(begin,minlen);
    }
};

?