/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0; while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}
}
应用：
最小覆盖子串
public String minWindow (String S, String T) {// write code hereint[] map = new int[128];//init map, 记录T中每个元素出现的次数for(int i = 0; i < T.length(); i++) {map[T.charAt(i)]++;}// begin end两个指针指向窗口的首位，d记录窗口的长度， counter记录T中还有几个字符没被窗口包含int begin = 0, end = 0, d = Integer.MAX_VALUE, counter = T.length(), head = 0;// end指针一直向后遍历while(end < S.length()) {// map[] > 0 说明该字符在T中出现，counter-- 表示对应的字符被包含在了窗口，counter--, 如果s中的字符没有在T中出现，则map[]中对应的字符-1后变为负值if(map[S.charAt(end++)]-- > 0) {counter--;}// 当counter==0时，说明窗口已经包含了T中的所有字符while (counter == 0) {if(end - begin < d) {d = end - (head = begin);}if(map[S.charAt(begin++)]++ == 0) { // begin开始后移，继续向后寻找。如果begin后移后指向的字符在map中==0，表示是在T中出现的，如果没有出现，map[]中的值会是负值。counter++; // 在T中的某个字符从窗口中移除，所以counter++。}}}return d==Integer.MAX_VALUE ? "" :S.substring(head, head+d);}
}