leetcode 76. 最小覆盖子串
给你一个字符串S、一个字符串T，请在字符串S里面找出：包含T所有字符的最小子串。
题解：
1.两个字符串
2.在包含T中所有字符的S子串中
3.找一个长度最小的
4.返回这个连续子串的内容
5.不要求T中字符连续形式存在S子串中
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案
解题思路：Hash+滑动窗口
-
因为是字符形式通过hash把字符映射到辅助数组中对应位置，与map存储键值对原理是一样的
-
窗口遍历字符到辅助数组的映射，并用一个计数器记录遍历S子串中包含T中子串的个数，个数小于T.size时是没有合格子串直到个数相等
-
个数相等则就有了合格子串，更新最小子串最小长度值和起始位置
-
然后开始从前向后缩短子串，也是左指针向后移动找更小的子串
-
注意处理左指针向后移动中如果去掉的是T中的字符，count计数减小
C/C++题解：
class Solution {
public:
string minWindow(string s, string t) {
int s_size = s.size(),t_size = t.size();
if(t_size == 0 || s_size < t_size) return "";//直接筛掉一部分
vector<int> vec(128,0); //hash
int min_left = -1,left = 0,min_len = INT_MAX,count = 0;
for(char c:t) vec[c]++; //字母映射到下标
for(int i = 0;i < s_size;i++){
if(--vec[s[i]] >= 0) count++; //遍历对count计数，直到T中所有字符出现在了子串中
while(count == t_size){ //如果t都包含在s中，计数相等
if(min_len > i - left + 1){ //当前找到的字符串与上一个合格字符串长度还小则更新
min_len = i - left + 1;//此时全部包含的字符串长度
min_left = left; }//min_left记录当前最小串的左起始位置
if(++vec[s[left]] > 0) //如果当前检查子串起始位置元素在t中
count--;//向左移动left则t在s子串中元素个数也会减少
left++; }//左指针向后移动缩小窗口
}//如果左起始位没变过则没有，否则有一起始位置min_left,长度为min_len的最小子串
return min_left == -1 ? "" : s.substr(min_left,min_len);}};
Debug结果：
Java题解：
class Solution {
public String minWindow(String s, String t) {
int s_size = s.length(),t_size = t.length();
if(t_size == 0 || s_size < t_size) return "";//直接筛掉一部分
int[] vec = new int[128]; //hash
int min_left = -1,left = 0,min_len = Integer.MAX_VALUE,count = 0;
for(char c:t.toCharArray()) vec[c]++; //字母映射到下标
for(int i = 0;i < s_size;i++){
if(--vec[s.charAt(i)] >= 0) count++; //遍历对count计数，直到T中所有字符出现在了子串中
while(count == t_size){ //如果t都包含在s中，计数相等
if(min_len > i - left + 1){ //当前找到的字符串与上一个合格字符串长度还小则更新
min_len = i - left + 1;//此时全部包含的字符串长度
min_left = left; } //min_left记录当前最小串的左起始位置
if(++vec[s.charAt(left)] > 0) //如果当前检查子串起始位置元素在t中
count--;//向左移动left则t在s子串中元素个数也会减少
left++; }//左指针向后移动缩小窗口
}//如果左起始位没变过则没有，否则有一起始位置min_left,长度为min_len的最小子串
return min_left == -1 ? "" : s.substring(min_left,min_left+min_len);}}
Debug结果：
Python题解：
class Solution(object):
def minWindow(self, s, t):
""":type s: str:type t: str
:rtype: str"""
vec=collections.defaultdict(int)
for c in t: vec[c]+=1 #字母映射到下标
i, t_size=0, len(t)
minLeft, minRight = 0,len(s)
for j,c in enumerate(s):
if vec[c]>0: t_size-=1 #遍历计数
vec[c]-=1
if t_size==0: #直到T中所有字符出现在了子串中
while True: #增加i，排除多余元素
c=s[i]
if vec[c]==0: #不在T中的值为-1，从左向后滑动
break #到第一个出现在T中字符位置
vec[c]+=1 #当前s中字符是T中的
i+=1 #左指针移动
if j-i<minRight-minLeft: #更新左右窗口
minLeft, minRight=i, j
vec[s[i]]+=1 #左指针向后移动缩小窗口
t_size+=1
i+=1
if minLeft == 0: return '' #最小索引没被更新过则没有子串
return s[minLeft:minRight+1] #否则返回查找子串
Debug结果：
更多题解移步公众号免费获取