转自：数据结构和算法
网上一网友感叹：事业编一年6万，干40年退休，总共挣240万，码农按一年60万工作5年算，总共挣300万，事业编再舒服有码农干五年退休舒服么？
真实情况是程序员很难一毕业就达到年薪60万，一般需要工作至少5年以上，即使达到也是少数，也只有在一线城市的大厂才有可能。而事业编一年6万明显有点低了，还有不能光看现在薪资，还要看退休工资。。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第76题：最小覆盖子串。
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
输入
：s = "ADOBECODEBANC", t = "ABC"
输出
："BANC"
解释
：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
输入
：s = "a", t = "a"
输出
："a"
解释
：整个字符串 s 是最小覆盖子串。
-
m == s.length
-
n == t.length
-
1 <= m, n <= 10^5
-
s 和 t 由英文字母组成
这题说的是找出 s 的一个最小子串，并且这个子串要涵盖 t 中的所有字符，其实就是一个大小可变的滑动窗口问题。
解决思路就是刚开始的时候左指针不动，右指针往右滑动，当窗口中包含 t 中所有字符的时候，说明找到了一个可行的解，但不一定是最优的，我们还需要缩小窗口来找到最优解。
这个时候右指针不动，左指针往右滑来缩小窗口找出最优解……。一直重复上面的过程，直到右指针不能在滑动为止，滑动的时候需要记录满足条件的窗口长度，保存最小长度即可，这个最小长度就最优解，这里画个图来看下。
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 if (map[s.charAt(right++)]-- > 0)
count--;// 覆盖一个减 1
while (count == 0) {// 如果全部覆盖，说明满足条件。
// 如果有更小的窗口就记录更小的窗口
if (right - left 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 "";
}
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 if (m[s[right++]]-- > 0)
count--;// 覆盖一个减 1
while (count == 0) {// 如果全部覆盖，说明满足条件。
// 如果有更小的窗口就记录更小的窗口
if (right - left windowMin = right - left;
strStart = left;
}
// 移动窗口左边界，如果有一个没覆盖，count加 1
if (m[s[left++]]++ == 0)
count++;
}
}
// 如果找到合适的窗口就截取，否则就返回空。
if (windowMin != INT_MAX)
return s.substr(strStart, windowMin);
return "";
}
char *minWindow(char *s, char *t) {
int m[128] = {0};
int
