LeetCode: Minimum Window Substring [076]
2020-12-13 02:11
标签：leetcode 算法 面试
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
Minimum window is
Note:
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
下面以题目中所给的例子为例看一下最小窗口搜索的全过程
LeetCode: Minimum Window Substring [076],搜素材,soscw.com LeetCode: Minimum Window Substring [076] 标签：leetcode 算法 面试 原文地址：http://blog.csdn.net/harryhuang1990/article/details/27519565【题目】
S = "ADOBECODEBANC"
T = "ABC""BANC".
If there is no such window in S that covers all characters in T, return the emtpy string "".【题意】
如果找到，则返回最小的窗口子串，如果找不到就返回""。
题目保证，如果存在最小窗口，那么有且仅有一个。
复杂度要求为O(n)
【思路】
2. 维护两个指针p1, p2分别指向窗口的头尾，p2依次向后扫描，并不断更新窗口中目标字符出现的次数，一旦T中的字符全部出现，则确定为一个符合条件的窗口, 此时收缩p1来最小化窗口。
3. 重复步骤2直到p2到达字符串S尾。
【代码】
class Solution {
public:
string minWindow(string S, string T) {
int sizeS = S.length();
int sizeT = T.length();
if(sizeS==0 || sizeT==0 || sizeT>sizeS)return "";
//建立目标词典
int targetmap[256]; //数组中的默认值不是0，必须进行初始化
int ansmap[256];
memset(targetmap, 0, sizeof(targetmap));
memset(ansmap, 0, sizeof(ansmap));
for(int i=0; i
文章标题：LeetCode: Minimum Window Substring [076]
文章链接：http://soscw.com/essay/25064.html