双指针算法之滑动窗口 | 力扣76.最小覆盖字串

• 本文讲解力扣76.最小覆盖字串问题
• 主要用到的是滑动窗口的思想

---

目录

• • 76.最小覆盖字串
  • • 题目：
    • 分析：
    • 步骤描述：
    • 复杂度分析：
    • 结果

76.最小覆盖字串

题目：

给定字符串 S 以及字符串 T ，求 S 种 包含 T 的最短连续子字符串的长度

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

要求 时间复杂度 ≤ O(n)

分析：

首先，返回的是字符串类型，想到使用 substr函数 截取对应的子串

使用数组，映射 T 中的字符情况，标记字符存在与否、对应的数量

使用滑动窗口的解法，可以解决大部分字符串匹配的问题~

步骤描述：

• L R 指针。都从最左端到最右端移动，且 L <= R，L 只能在R 左边或者重合
• 挪动指针，根据映射情况，找到满足要求的窗口
• 找到一个窗口，继续挪动，不影响结果的情况下寻找其它满足要求的窗口，取最小值
• 挪动的时候，注意 L 指针会更新，所以会“抛出”窗口原来最左边的字符，需要处理“如果窗口抛出的是T中存在的某个字符”这种情况

class Solution { public:string minWindow(string s, string T) {vector<int> chars(128,0); vector<bool> flag(128,false); // 记录字符是否在 T 中存在// 映射 T 中的字符情况for(int i = 0; i < T.size(); ++i){flag[T[i]] = true;++chars[T[i]]; // 字符的数量}int cnt =0; // 判断 T的字符是不是都找完了int l=0,min_l=0;int min_size=s.size()+1;for (int r = 0; r < s.size(); ++r) {if (flag[s[r]]) {if (--chars[s[r]] >=0) {++cnt;}// 窗口包含了全部字符之后， L 指针继续后移，继续寻找其它满足情况，找最小窗口while (cnt == T.size()) {if (r-l+1 < min_size) {min_l = l;min_size = r-l+1;}// 窗口后挪，左边会“抛出”// 如果抛出的是T中存在的某个字符if (flag[s[l]] && ++chars[s[l]] >0) {--cnt;}++l;}}}return min_size >s.size()?"":s.substr(min_l, min_size);} };

复杂度分析：

虽然代码使用了 for 和 while嵌套，但是 while 只是用来滑动的，所以时间复杂度是满足要求的 O(n)

结果

总结

以上是生活随笔为你收集整理的双指针算法之滑动窗口 | 力扣76.最小覆盖字串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。