滑动窗口
关注三个问题:
1、什么时候应该扩大窗口?
2、什么时候应该缩小窗口?
3、什么时候应该更新答案?
/* 滑动窗口算法框架 */
void slidingWindow(string s) {
// 用合适的数据结构记录窗口中的数据
unordered_map<char, int> window;
int left = 0, right = 0; //区间设置为左闭右开
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
window.add(c);
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时,可能导致超时
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
window.remove(d);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}