首页 > 代码库 > LeetCode-Minimum Window Substring-最小窗口子串-滑动窗口算法（尺取法）
LeetCode-Minimum Window Substring-最小窗口子串-滑动窗口算法（尺取法）
https://oj.leetcode.com/problems/minimum-window-substring/
线性复杂度的限制下，考虑使用滑动窗口法。这个方法的思路就是维持一个窗口，窗口向右边界扩张以满足限制条件。窗口左边界收缩以尽量使其最小。
注意这个题目可能是一个典型的滑动窗口方法的实现。外部循环移动左边界i，循环内部扩张右边界p以满足限制条件。并且内外都有终止可能。
使用两个map和一个计数变量以快速统计条件限制的满足情况。
class Solution {public: int n,m; string minWindow(string S, string T) { map <char,int> cm; map <char,int> stat; n=S.length(); m=T.length(); for (int i=0;i<m;i++){ if (cm.find(T[i])==cm.end()){ cm[T[i]]=1; } else{ cm[T[i]]++; } stat[T[i]]=0; } int res=numeric_limits<int>::max(); typedef pair <int,int> scpair; scpair minw; int q=0; int count=0; for (int i=0;i<n;i++){ bool endFlag=false; while(count<m){ q++; if (q>n){ endFlag=true; break; } if (cm.find(S[q-1])==cm.end()){continue;} if (stat[S[q-1]]<cm[S[q-1]]){ count++; } stat[S[q-1]]++; } if (endFlag){break;} if (res > q-i){ res=q-i; minw=scpair(i,q); } if (cm.find(S[i])==cm.end()){continue;} stat[S[i]]--; if (stat[S[i]]<cm[S[i]]){count--;} } if (res>n){return "";}//no win return S.substr(minw.first,minw.second-minw.first); }};
LeetCode-Minimum Window Substring-最小窗口子串-滑动窗口算法（尺取法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。