【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串

本文主要是介绍【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

送给大家一句话：

充满着欢乐与斗争精神的人们，永远带着欢乐，欢迎雷霆与阳光。 —— 赫胥黎

前言

相信通过前两篇的文章的讲解，大家已经对滑动窗口有了较深的认识，今天我们来挑战一下！！！
来做两道困难级的题目。

Leetcode 30. 串联所有单词的子串

家人们！！！上链接！！！30. 串联所有单词的子串

题目描述

根据题目描述，这道题看起来很是复杂呢！？！？
我们要在一个字符串中寻找包含words的所有单词的子串，并会返回对应的开始位置（开始索引）。看这描述十分类似这道题目 438. 找到字符串中所有字母异位词 ，一个是寻找异位词，一个是寻找"异位单词串"。本质是十分相似的。
来看一个样例：

• 输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
• 输出：[0,9]
• 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
  子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
  子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
• 输出顺序无关紧要。返回 [9,0] 也是可以的。

根据这样例，更容易想象为是如同字母一样。

算法思路

我们先把每个单词抽象为一个字母（方便我们梳理思路），我们只需要找到一个子串中有所有的“字母”即可。
那么，我们来看最简单的算法：暴力枚举。就是遍历所有的子串，以样例来说：

1. bar foo the foo bar man （注意步长是单词的长度），从左到右依次遍历，寻找满足条件的子串。

2. 我们来思考一下，当该躺不满足条件时：
   

   很明显，无需把right重新移动的到left的位置重新开始，直接继续进行移动就可以。

3. 所以此时构成滑动窗口的条件两个指针移动方向一致

那么我们就按照滑动窗口的解题模版来思考细节：

• 进窗口
• 判断
• 出窗口
• 更新结果（位置待定）

首先我们要解决的是个一般性问题：s 字符串的长度一定是单词的整数倍吗？？？
显然不是！
那么就要进行多次滑动窗口！保证可以遍历到所有可能的子串。那进行几次呢？？？

可以看出来只需要进行单词个数次的循环即可！！！再多就发生重复了！

这样大致的框架就有了，剩下的就是然后判断单词是否满足条件。
依旧时候使用哈希算法，利用无向图来模拟哈希表（string 映射 int）。

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {//预备工作//哈希表1unordered_map<string,int> hash1;for(auto ch : words) hash1[ch] ++; //对words进行处理// 基本变量int len = words[0].size(); //单词长度（步长） int m = words.size();//单词个数int n = s.size();//字符串长度//答案vector<int> ans;//多次进行滑动窗口for(int i = 0;i < len;i++){//哈希表2 用来进行比较unordered_map<string,int> hash2;//进窗口 注意一次移动的步长 注意结束条件（保证最后一个是完整单词，不然会发生越界）for(int left = i ,right = i ,count = 0; right + len <= n ; right += len ){string in = s.substr(right,len);//进窗口 维护count++ （有效单词数加一）if(++hash2[in] <= hash1[in]){count++;}//判断是否超出长度if(right - left + 1 > m * len){string out = s.substr(left,len);//出窗口 维护countif(hash2[out]-- <= hash1[out]) count--;left += len;}//满足条件  更新结果if(count == m){ans.push_back(left);}} }return ans;}
};

我们提交：过啦！！！！

Leetcode 76. 最小覆盖子串

家人们！！！ 上链接！！！76. 最小覆盖子串

题目描述

根据题目描述，我们需要再字符串中寻找能够覆盖 t 中所有字符的 最短子串，这个“覆盖”是包含 t 中的每个字母，不用管顺序。来看样例：

• 输入：s = “ADOBECODEBANC”, t = “ABC”
• 输出：“BANC”
• 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

看了样例，应该就理解了这个“覆盖”：

1. 对应字母个数必须大于等于 t 中字母个数
2. 可以包含其它字母

算法思路

先来最直接的办法 — 暴力枚举，我们来看暴力算法是如何进行的：

1. 首先找到一个包含于 t 的字母
2. 然后从这个位置开始遍历
3. 直到满足 t 中的每个字母都能在该子串中找到
4. 然后再找到下一个包含于 t 的字母 重复 1 - 3

这样就完成了任务，那么如何进行优化呢？？？
根据暴力的步骤，我们可以看出来两个指针的移动方向是一致的，所以就可以进行滑动窗口算法了。
那么我们就按照滑动窗口的解题模版来思考细节：

• 进窗口
• 判断
• 出窗口
• 更新结果（位置待定）

这个判断要怎样进行判断？？？
肯定是使用哈希算法，但是如何保证对应字母个数必须大于等于 t 中字母个数呢？？？
这一步与之前的判断略有不同，因为我们可以多字母,来看代码：

class Solution {
public:string minWindow(string s, string t) {//滑动窗口 + 哈希算法//准备工作int kinds = 0; //字母种类 方便判断int hash1[128] = {0}; //哈希表1 因为只有使用数组比较方便//遍历所有字母 确定个数for (auto ch : t) if (hash1[ch]++ == 0) kinds++;// 长度 int n = s.size();//哈希表2 用来比较int hash2[128] = { 0 }; int begin = -1 ,minlen = INT_MAX;for(int left = 0,right = 0 ,count = 0;right < n;right++){char in = s[right];//进窗口 维护count (对应字母相等时更新 保证满足条件 有效字母加一)if(++hash2[in] == hash1[in]) count++;//判断while(count == kinds){//更新结果if(right - left + 1 < minlen){minlen = right - left + 1;begin = left;}char out = s[left];//出窗口 维护count (相等时出窗口 有效字母减少)if(hash2[out]-- == hash1[out]) count--;left++;}}return begin == -1 ? "" : s.substr(begin,minlen);}
};

提交：过啦！！！！！！

经过这两道题目的书写，相信大家一定深刻认识到了滑动窗口的使用方法！！！
下面请大家继续刷题吧！！！

Thanks♪(･ω･)ﾉ 谢谢阅读！！！

下一篇文章见！！！

这篇关于【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---