用两个指针分别记录窗口的左右边界,移动指针时忽略那些出现在S种但是没有出现在T中的字符
1. 扩展窗口。向右移动右指针,当窗口内的字符即将多于T内的字符时,停止右移
2. 收缩窗口。向右调整左指针,当窗口内的字符即将少于T内的字符时,停止右移
3. 统计结果。如果窗口内的字符包含了T内的所有字符,且窗口更小,更新最小窗口
4. 继续下一个周期(返回1)
大致思路就是这样了,在具体实现中我用了一个left变量记录当前还未完全包含的非重字符数量,比如当前窗口还差2个a和3个b,则left=2,这样,当left=0时就知道已经包含了所有T的字符。
代码:
string minWindow(string S, string T) {
map<char, int> tMap;
map<char, int> windowMap;
int sLen = S.length();
int tLen = T.length();
string window = "";
int left = ; for (int i = ; i < tLen; i++)
tMap[T[i]]++;
left = tMap.size(); // 扩展
for (int l = , r = ; r < sLen;) {
for (bool shrink = false; r < sLen && !shrink; r++) {
if (tMap.find(S[r]) != tMap.end()) {
windowMap[S[r]]++;
if (windowMap[S[r]] == tMap[S[r]])
left--;
shrink = windowMap[S[r]] >= tMap[S[r]];
}
} // 收缩
for (; l < r; l++) {
if (tMap.find(S[l]) != tMap.end()) {
if (windowMap[S[l]] <= tMap[S[l]])
break;
windowMap[S[l]]--;
}
} if (!left && (window.empty() || window.length() > r - l))
window = S.substr(l, r - l);
} return window;
}