力扣-76题最小覆盖子串（C++）- 滑动窗口

深碍√TFBOYSˉ_ 2022-09-04 06:47 180阅读 0赞

题目链接：[https://leetcode-cn.com/problems/minimum-window-substring/][https_leetcode-cn.com_problems_minimum-window-substring]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][57eaa21ef4c94da18416eed6a3a526d7.png]

class Solution {
        
    public:
        string minWindow(string s, string t) {
        
            unordered_map<char,int> hs,ht;
    
            for(auto e:t) ht[e]++;
    
            string result="";
            int valid_count=0; 
            
            for(int i=0,j=0;i<s.size();i++){
        
                hs[s[i]]++;
                if(hs[s[i]]<=ht[s[i]]) valid_count++;//说明是有效字符
    
                while(hs[s[j]]>ht[s[j]]){
        //说明当前这个是多余的字符，目的，去掉多余的字符
                    hs[s[j]]--;
                    j++;
                }
    
                if(valid_count==t.size()){
        //当前是有效窗口
                    if(i-j+1<result.size()||result=="") result=s.substr(j,i-j+1);
                }
    
            }
    
            return result;
        }
    };

[https_leetcode-cn.com_problems_minimum-window-substring]: https://leetcode-cn.com/problems/minimum-window-substring/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/5801dfafcbda4109a816b5f4af2d3d20.png
[57eaa21ef4c94da18416eed6a3a526d7.png]: /images/20220829/bcd6c0e003ed4008bf253174a102126d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 76. 最小覆盖子串（滑动指针）

76. 最小覆盖子串题目解题思路代码题目给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中

喜欢ヅ旅行/ 2023年10月05日 20:12/ 0 赞/ 20 阅读

相关 76. 最小覆盖子串

给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""`

深藏阁楼爱情的钟/ 2023年10月04日 10:26/ 0 赞/ 33 阅读

相关 76最小覆盖子串

一、前言标签：字符串滑动窗口。问题来源LeetCode 76 难度：困难。问题链接：[https://leetcode-cn.com/problems/mini

系统管理员/ 2023年03月01日 11:54/ 0 赞/ 10 阅读

相关 Leetcode-76. 最小覆盖子串（滑动窗口）

76. 最小覆盖子串（滑动窗口） > 1. 最小覆盖子串（滑动窗口） > 链接：[https://leetcode-cn.com/problems/mini

逃离我推掉我的手/ 2023年02月11日 13:28/ 0 赞/ 16 阅读

相关最小覆盖子串Java版（力扣）

[最小覆盖子串][Link 1] 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串

小灰灰/ 2022年11月10日 05:26/ 0 赞/ 132 阅读

相关 76. 最小覆盖子串

链接：[https://leetcode-cn.com/problems/minimum-window-substring/][https_leetcode-cn.com_pr

电玩女神/ 2022年10月13日 01:55/ 0 赞/ 212 阅读

相关 76. 最小覆盖子串

先上滑动窗口模板 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

﹏ヽ暗。殇╰゛Y/ 2022年10月09日 12:10/ 0 赞/ 212 阅读

相关 LeetCode 最小覆盖子串【滑动窗口】

1 最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

叁歲伎倆/ 2022年09月10日 12:08/ 0 赞/ 189 阅读

相关力扣-76题最小覆盖子串（C++）- 滑动窗口

题目链接：[https://leetcode-cn.com/problems/minimum-window-substring/][https_leetcode-cn.com_

深碍√TFBOYSˉ_/ 2022年09月04日 06:47/ 0 赞/ 181 阅读

相关 Leetcode 76. 最小覆盖子串(滑动窗口算法 YYDS)

题目重述给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意

àì夳堔傛蜴生んèń/ 2022年08月31日 12:23/ 0 赞/ 169 阅读