考公放宽至40岁了，我觉得我可以闯一闯了。。。

专栏：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算法文档 。