76. 最小覆盖子串

76. 最小覆盖子串

不要看他说什么“困难”，不困难，和209,904一个水平。

这道题就是滑动窗口啊，题干里都直接出现窗口这个词了。

他想要的是合法情况下的最小窗口，这个和209的特性是相同的。

那剩下就是进出窗口和合法性的判断了。这个要的是字母数量，那其实和904那个水果是差不多的，只不过给了你个t字符串，需要达到t的那个种类和数量。所以类似的，也是一个数组记录所有的数量，一个种类变量记录有几个字母。

还有一个就是函数的返回值，不再是209和904返回最大值最小值，而是要返回那个字符串是什么。那也很简单，在更新最小值的时候记录位置（res_i）就好了，最后用s的substr方法来取出来。

完整代码

class Solution {
  public:
	string minWindow(string s, string t)
	{
        int i = 0, m = s.length(), n = t.size(), res_len = m+1, res_i = 0;
        // 统计t的字符数量和字符种类
        vector<int> letters(128,0);
        int letter_cnt = 0;
        for(int i = 0;i<n;i++){
            if(letters[t[i]] == 0){
                letter_cnt++;
            }
			letters[t[i]]++;
		}
        for(int j = 0;j<m;j++){
			// s[j]进入窗口,对应字符数量-1,对应字符数量0，字符种类-1
			letters[s[j]]--;
            if(letters[s[j]] == 0){
                letter_cnt--;
            }
            while(letter_cnt == 0){
                // res_len = min(res_len, j-i+1);
                if(j-i+1 < res_len){
                    res_len = j-i+1;
                    res_i = i;
                }
				// s[i]退出窗口，对应字符数量0，字符种类+1,然后对应字符数量+1
				if (letters[s[i]] == 0) {
					letter_cnt++;
				}
				letters[s[i]]++;
                i++;
			}
        }
        if(res_len == m+1){
            return "";
        }
        return s.substr(res_i, res_len);
	}
};

总体上，整个代码的框架和209要更相近一点，改的只有进出窗口、合法性的判断和函数返回值这3个东西。