网站开发公司郑州,电信备案网站打不开,公司ppt简介模板,合肥网络推广优化公司1. 题目
给你一个字符串 S、一个字符串 T#xff0c;请在字符串 S 里面找出#xff1a;包含 T 所有字母的最小子串。
示例#xff1a;
输入: S ADOBECODEBANC, T ABC
输出: BANC说明#xff1a;
如果 S 中不存这样的子串#xff…1. 题目
给你一个字符串 S、一个字符串 T请在字符串 S 里面找出包含 T 所有字母的最小子串。
示例
输入: S ADOBECODEBANC, T ABC
输出: BANC说明
如果 S 中不存这样的子串则返回空字符串 。
如果 S 中存在这样的子串我们保证它是唯一的答案。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-window-substring 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 滑动窗口
类似题目LeetCode 727. 最小窗口子序列滑动窗口
对t中的字符计数设置窗口leftright一开始right右移直到窗口包含所有t中字符然后开始右移左端点字符移除直到有效的t字符数不够了再返回上面循环右移右端点
class Solution {
public:string minWindow(string s, string t) {if(s || t || s.size() t.size())return ;unordered_mapchar,int m;for(char c : t)m[c];string ans;int left 0, right 0, len 0, minLen INT_MAX;for( ; right s.size(); right){m[s[right]]--;//希望t中的字符计数为0为正说明还不够为负说明多了if(m[s[right]]0)//不存在t中的字符计数是负的存在t中且多出的计数也为负len;while(len t.size())//窗口包含所有的t的字符了{if(right-left1 minLen)//更新最小窗口长度{minLen right-left1;ans s.substr(left,minLen);}m[s[left]];//缩短left计数1(非t字符趋近0t中字符计数由-或者0往上增加)if(m[s[left]] 0)//t中的字符才有可能大于0目标t字符数不够--len;//窗口包含t的字符数-1left;//缩短左窗口直到len不等于t的长度有效字符数不够了}}return ans;}
};
