跳转至

76 最小覆盖子串

又是子串,我们立即想到使用滑动窗口

思路

  1. 首先想到的肯定是暴力解法:暴力枚举 + 哈希表
  2. 然后在分析的过程中,发现双指针同向不回退,就可以利用这个单调性,联想到滑动窗口解法:滑动窗口 + 哈希表

解题方法

  1. 先创建两个哈希表,用来统计两个字符串中字符出现的次数
  2. 再将要覆盖的字符串t,存入哈希表baseHash
  3. 设置pos和minLen,用来记录子串的初始位置和最小长度(这步很关键,我们可以等循环结束再拷贝子串,而不是循环中,减少了很多时间开销)
  4. 其次设置count,用来记录curHash中的有效字符个数(这步优化,可以让我们不用每次都一一比较两个哈希表,而是比较count是否达到t的有效字符个数)

接下来,是正常的滑动窗口四步走(详见代码):

  • 进窗口
  • 判断
  • 出窗口
  • 处理结果(这步的位置根据题目要求而变化)

复杂度

  • 时间复杂度:O(m+n)
  • 空间复杂度:O(1)
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> window, need;
        // 记录t的字符个数
        for(char c : t){
            need[c]++;
        }
        int left = 0, right = 0;
        // valid记录满足的字符个数
        int valid = 0;
        int start = 0, len = INT_MAX;
        while(right < s.size()){
            char c = s[right];
            right++;

            // 更新数据
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]){
                    valid++;
                }
            }

            while(valid == need.size()){
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                char d = s[left];
                left++;

                // 更新数据
                if(need.count(d)){
                    if(window[d] == need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};