专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近关于考公年龄放宽到40岁这件事在网上有引起了热议，不过只是在上海、浙江、江苏、山东等个别省份放开，其他省份目前还没有放开，有网友建议要全部放开。
我查了下上海的虽然放开了，但也有很大的限制，比如硕士，博士可以放宽到40岁，还有报考工青妇机关和妇联系统职位的也放宽到40岁以下，放的还是不彻底。虽然是一次小小的尝试，希望以后能全部放开，就像一位网友说的：从川普80岁竞选总统职位来看，年龄不应该成为职业门槛。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第76题：最小覆盖子串。
问题描述
来源：LeetCode第76题
难度：困难
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
示例1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
m == s.length
n == t.length
1 <= m, n <= 10^5
s 和 t 由英文字母组成
问题分析
这题说的是找出 s 的一个最小子串，并且这个子串要涵盖 t 中的所有字符，其实就是一个大小可变的滑动窗口问题。
解决思路就是刚开始的时候左指针不动，右指针往右滑动，当窗口中包含 t 中所有字符的时候，说明找到了一个可行的解，但不一定是最优的，我们还需要缩小窗口来找到最优解。
这个时候右指针不动，左指针往右滑来缩小窗口找出最优解……。一直重复上面的过程，直到右指针不能在滑动为止，滑动的时候需要记录满足条件的窗口长度，保存最小长度即可，这个最小长度就最优解，这里画个图来看下。
JAVA：
public String minWindow(String s, String t) { int[] map = new int[128]; // 记录字符串t中每个字符的数量 for (char ch : t.toCharArray()) map[ch]++; int count = t.length();// 字符串t的数量 int left = 0;// 窗口的左边界 int right = 0;// 窗口的右边界 // 覆盖t的最小长度 int windowMin = Integer.MAX_VALUE; int strStart = 0;// 覆盖字符串t开始的位置，为了后面截取。 while (right < s.length()) { if (map[s.charAt(right++)]-- > 0) count--;// 覆盖一个减 1 while (count == 0) {// 如果全部覆盖，说明满足条件。 // 如果有更小的窗口就记录更小的窗口 if (right - left < windowMin) { windowMin = right - left; strStart = left; } // 移动窗口左边界，如果有一个没覆盖，count加 1 if (map[s.charAt(left++)]++ == 0) count++; } } // 如果找到合适的窗口就截取，否则就返回空。 if (windowMin != Integer.MAX_VALUE) return s.substring(strStart, strStart + windowMin); return ""; }C++：
public: string minWindow(string s, string t) { int m[128]; // 记录字符串t中每个字符的数量 for (char ch: t) m[ch]++; int count = t.length();// 字符串t的数量 int left = 0;// 窗口的左边界 int right = 0;// 窗口的右边界 // 覆盖t的最小长度 int windowMin = INT_MAX; int strStart = 0;// 覆盖字符串t开始的位置，为了后面截取。 while (right < s.length()) { if (m[s[right++]]-- > 0) count--;// 覆盖一个减 1 while (count == 0) {// 如果全部覆盖，说明满足条件。 // 如果有更小的窗口就记录更小的窗口 if (right - left < windowMin) { windowMin = right - left; strStart = left; } // 移动窗口左边界，如果有一个没覆盖，count加 1 if (m[s[left++]]++ == 0) count++; } } // 如果找到合适的窗口就截取，否则就返回空。 if (windowMin != INT_MAX) return s.substr(strStart, windowMin); return ""; }Python：
def minWindow(self, s: str, t: str) -> str: map = [0] * 128 # 记录字符串t中每个字符的数量 for ch in t: map[ord(ch)] += 1 # left窗口的左边界,right窗口的右边界,count字符串t的数量 left, right, count = 0, 0, len(t) # windowMin覆盖t的最小长度,strStart覆盖字符串t开始的位置，为了后面截取。 windowMin, strStart = 2 ** 31, 0 while right < len(s): if map[ord(s[right])] > 0: count -= 1 # 覆盖一个减 1 map[ord(s[right])] -= 1 right += 1 while count == 0: # 如果全部覆盖，说明满足条件。 # 如果有更小的窗口就记录更小的窗口 if right - left < windowMin: windowMin = right - left strStart = left # 移动窗口左边界，如果有一个没覆盖，count加 1 if map[ord(s[left])] == 0: count += 1 map[ord(s[left])] += 1 left += 1 # 如果找到合适的窗口就截取，否则就返回空。 if windowMin != 2 ** 31: return s[strStart: strStart + windowMin] return ""笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴