四、滑动窗口

4.1 模板

/* 滑动窗口算法框架 */
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++;// 进行窗口内数据的一系列更新...// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}
}

需要变化的地方

• 1、右指针右移之后窗口数据更新
• 2、判断窗口是否要收缩
• 3、右指针右移之后窗口数据更新
• 4、根据题意计算结果

4.2 示例

4.2.1 最小覆盖子串

76. 最小覆盖子串

// 使用Map的存储方式
class Solution {public String minWindow(String s, String t) {// 1、创建用于保存滑动窗口包含的字符集的mapMap<Character,Integer> winChars =  new HashMap<>();// 2、创建保存子串中的字符集的map(注意重复的字符会累计次数)Map<Character,Integer> tChars = new HashMap<>();Integer temp;for(char c:t.toCharArray()){tChars.put(c,(temp=tChars.get(c)) == null?1:(temp+1));}int tCharNum = tChars.size(); // 子串中不同字符的个数int winCharNum = 0; // 滑动窗口中已匹配子串字符的个数（相同的字符要个数上匹配）int i = 0,j = 0; // 定义滑动窗口的左右边界int start = 0,end = 0; // 定义最终的滑动窗口的左右边界（即：最小尺寸的滑动窗口）int minWinLength = Integer.MAX_VALUE; // 初始化最小的滑动窗口值// 基于滑动窗口//先右移右指针直至包含所有的子串中的字符集, 再进行滑动窗口左边界右移while(j < s.length()){char c = s.charAt(j);if(tChars.get(c) != null){ // 若是子串中的字符, 记录当前的字符winChars.put(c,(temp=winChars.get(c)) == null?1:(temp+1));if(winChars.get(c).equals(tChars.get(c))){ // 判断是否已经有字符被完全匹配完（个数）winCharNum++;}}j++; // 右移滑动窗口，注意此处操作会指向最小窗口右边界的下一个位置（由于字符子串获取是左闭右开）// 右移左边界（即：滑动窗口中已匹配完所有的子串字符）while(winCharNum == tCharNum){// 记录当前的滑动窗口长度if(j - i < minWinLength){start = i;end = j;minWinLength = j - i;}char leftChar = s.charAt(i);if(tChars.get(leftChar) != null){ // 若右移左边界排除了一个子串中的字符if(winChars.get(leftChar).equals(tChars.get(leftChar))){ // 该字符刚好个数完全匹配，则右移左边界会使总匹配个数减一// 也可能滑动窗口中匹配的字符个数大于子串中该字符的个数winCharNum--;}winChars.put(leftChar,winChars.get(leftChar)-1); // 更新滑动窗口中的字符集}i++;}}if(minWinLength == Integer.MAX_VALUE){ // 若没有更新，则返回空串return "";}return s.substring(start,end);}
}

// 使用数组的存储方式
class Solution {
public String minWindow(String s, String t) {// 技巧：用数组代替Map// 保存滑动窗口字符集int[] winMap = new int[256];// 保存需要出现的字符集int[] tMap = new int[256];for (char c : t.toCharArray()) {tMap[c]++;}// 计算共出现了多少不同的字符int charNum = 0;for (int n : tMap) {if (n > 0) {charNum++;}}// 滑动窗口左右边界int left = 0;int right = 0;// 匹配数int match = 0;// 窗口调整前暂存原窗口边界int start = 0;int end = 0;// 窗口长度的最小值int minValue = Integer.MAX_VALUE;while (right < s.length()) {char c = s.charAt(right);// 在需要的字符集里面，添加到窗口字符集里面if (tMap[c] != 0) {winMap[c]++;// 如果当前字符的数量匹配需要的字符的数量，则match值+1if (tMap[c] == winMap[c]) {match++;}}right++;// 当所有字符数量都匹配之后，开始缩紧窗口while (match == charNum) {// 获取结果if (right - left < minValue) {minValue = right - left;start = left;end = right;}char leftChar = s.charAt(left);// 左指针指向不在需要字符集则直接跳过if (tMap[leftChar] != 0) {// 左指针指向字符数量和需要的字符相等时，右移之后match值就不匹配则减一if (winMap[leftChar] == tMap[leftChar]) {match--;}winMap[leftChar]--;}left++;}}if (minValue == Integer.MAX_VALUE) {return "";}return s.substring(start, end);
}
}

4.2.2 字符串的排列

567. 字符串的排列

// 使用数组的存储方式
class Solution {public boolean checkInclusion(String s1, String s2) {// 创建保存滑动窗口中字符集的数组int[] wChars = new int[256];// 创建保存子串字符集的数组（累计字符个数）int[] tChars = new int[256];// 记录子串的字符for(char c:s1.toCharArray()){tChars[c]++;}int tCharNum = 0; // 子串不同字符的个数 for(int i:tChars){if(i>0){tCharNum++;}}int left = 0,right = 0; // 滑动窗口的左右边界int winCharNum = 0; // 记录滑动窗口中匹配字符的数量（具有多个相同字符需要被匹配完）// 滑动窗口算法// 先右移有边界直至窗口内匹配完所有子串字符，接着做一左边界while(right < s2.length()){char c = s2.charAt(right);if(tChars[c] != 0){wChars[c]++; // 记录当前字符if(wChars[c] == tChars[c]){ // 对某一个字符完全匹配后记录数量winCharNum++;}}right++; // 此时right指向窗口右边界的右边一个位置// 右移左边界while(winCharNum == tCharNum){c = s2.charAt(left);if(tChars[c] != 0){if(wChars[c] == tChars[c]){ // 若当前字符数刚好等于子串中该字符的数量，则再减少一个就减少匹配数winCharNum--;if(right - left == s1.length()){ // 若窗口长度等于子串长度则为排列匹配return true;}}// 更新窗口中字符的信息wChars[c]--;}left++;}}return false;}
}

4.2.3 找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词

class Solution {public List<Integer> findAnagrams(String s, String p) {// 创建保存窗口中字符集的数组int[] wChars = new int[256];// 创建保存子串的字符集信息（累计字符个数）int[] tChars = new int[256];for(char c:p.toCharArray()){tChars[c]++;}// 记录子串中不同字符的数量int tCharsNum = 0;for(int i:tChars){if(i>0){tCharsNum++;}}int left = 0, right = 0; // 定义滑动窗口的左右边界int wCharsNum = 0; // 记录窗口中匹配的字符个数（相同字符需数量匹配完）// 记录结果List<Integer> result = new ArrayList<>();// 滑动窗口算法// 先右移有边界直至窗口匹配完所有子串的字符，然后右移左边界while(right < s.length()){char c = s.charAt(right);if(tChars[c] != 0){ // 当前字符为子串中出现的字符wChars[c]++; // 窗口中记录当前字符if(wChars[c] == tChars[c]){ // 字符数量匹配完则记录一个字符数量wCharsNum++;}}right++;// 右移左边界while(wCharsNum == tCharsNum){c = s.charAt(left);if(tChars[c] != 0){ // 当前字符为子串中出现的字符if(tChars[c] == wChars[c]){ // 若数量相等，则取出当前字符后则记录数少1wCharsNum--;if(right - left == p.length()){ // 当前left为满足匹配要求的临界边界；right则为右边界的后面一个位置。相等时则意味则排列匹配// 记录左边界作为结果result.add(left);}}// 更新窗口字符信息wChars[c]--;}left++;}}return result;}
}

4.2.4 无重复字符的最长子串

3. 无重复字符的最长子串

class Solution {public int lengthOfLongestSubstring(String s) {if(s.length() < 2){return s.length();}// 保存窗口中的字符集信息int[] wChars = new int[256];int maxSubLength = 0;int left = 0, right = 0; // 定义滑动窗口的左右边界while(right < s.length()){char c = s.charAt(right);right++;wChars[c]++; // 记录窗口中的字符信息// 右移左边界收缩窗口while(wChars[c] > 1){char leftChar = s.charAt(left);left++;wChars[leftChar]--;}maxSubLength = Math.max(maxSubLength,right - left);}return maxSubLength;}
}