299-最小覆盖子串

Dear 丶 2023-01-17 03:21 135阅读 0赞

**题目如下：**  
给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：  
输入：S = “ADOBECODEBANC”, T = “ABC”  
输出：“BANC”

提示：  
如果 S 中不存这样的子串，则返回空字符串 “”。  
如果 S 中存在这样的子串，我们保证它是唯一的答案。

## 解题代码如下 ##

#include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    
    string minWindow(string s, string t)
    {
        
        vector<int> need(128, 0);
        for (char ch : t)
        {
        
            need[ch]++;
        }
        int start = 0, left = 0, right = 0, minLen = INT_MAX;
        int len = s.length();
        int cnt = t.length();
        while (right < len)
        {
        
            if (need[s[right]] > 0)
            {
        
                cnt--;
            }
            need[s[right]]--;
            if (cnt == 0) //第一次找到了所有串 移动左边指针
            {
        
                while (left < right && need[s[left]] < 0)
                {
        
                    need[s[left++]]++;
                }
                //出去以后更新最大长度
                if (right - left + 1 < minLen)
                {
        
                    start = left;
                    minLen = right - left + 1;
                }
                //更新完毕之后 继续左移动
                need[s[left++]]++;
                cnt++; //需要的字符++
            }
            right++;
        }
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
    
    int main()
    {
        
        string S = "ADOBECODEBANC";
        string T = "ABC";
        cout << minWindow(S, T);
        return 0;
    }

## 运行程序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/374c7f90d3f048b9afafdd163af67b9a.png