本章总结一下滑动窗口的解题思路：
- 在字符串中使用双指针 left 和 right 围成的一个左闭右开的区域作为一个窗口。
- 不断将 right 向右滑动，直到窗口中的字符串符合条件。
- 此时将 left 向右滑动，直到窗口中的字符串不符合条件，期间需不断的更新结果。
- 最后重复前两步，直到 right 指针达到尽头。
需要的变量：
- 需要维护两个map数组，need和window，分别记录所需要的字符及个数，和滑动窗口中的字符及个数。
- 左右指针left 和 right ，分别初始化为0。
- valid 用于记录窗口中符合条件的字符数，初始化为0。
leetcode76、最小覆盖子串
java代码如下：
class Solution {public String minWindow(String s, String t) {HashMap<Character,Integer> need = new HashMap<>(); //所需要的字符及个数HashMap<Character,Integer> window = new HashMap<>(); //滑动窗口内的符合need的字符及个数//滑动窗口的左右指针int left = 0, right = 0;int valid = 0;for(char c : t.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}//最小覆盖子串的起始索引及长度int start = 0, len = Integer.MAX_VALUE;while(right < s.length()){char c = s.charAt(right);//右移窗口right++;//更新窗口内数据if(need.containsKey(c)){window.put(c,window.getOrDefault(c,0)+1);if(window.get(c).equals(need.get(c))){valid++;}}//判断窗口是否需要收缩while(valid == need.size()){//更新最小覆盖子串if(right - left < len){start = left;len = right - left;}char d = s.charAt(left);//左移窗口left++;//更新窗口数据if(need.containsKey(d)){if(window.get(d).equals(need.get(d))){valid--;}window.put(d,window.get(d)-1);}}}if(len == Integer.MAX_VALUE) return "";return s.substring(start,start+len);}
}leetcode438、找到字符串中所有字母异位词
除了判断窗口是否要收缩的代码不一样，其他基本都一样，代码如下：
class Solution {public List<Integer> findAnagrams(String s, String p) {Map<Character,Integer> need = new HashMap<>();Map<Character,Integer> window = new HashMap<>();int left = 0, right = 0;int valid = 0;List<Integer> ans = new ArrayList<>();for(Character c : p.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}while(right < s.length()){char c = s.charAt(right);right++;if(need.containsKey(c)){window.put(c,window.getOrDefault(c,0)+1);if(window.get(c).equals(need.get(c))){valid++;}}while(right - left >= p.length()){if(valid == need.size()){ans.add(left);}char d = s.charAt(left);left++;if(need.containsKey(d)){if(window.get(d).equals(need.get(d))){valid--;}window.put(d,window.get(d)-1);}}}return ans;}
}leetcode3、无重复字符的最长子串
本题不需要 need，并且判断是否收缩的代码逻辑为：当前窗口是否存在重复字符。 java代码如下：
class Solution {public int lengthOfLongestSubstring(String s) {Map<Character,Integer> window = new HashMap<>();int left = 0, right = 0;int ans = 0;while(right < s.length()){char c = s.charAt(right);right++;window.put(c,window.getOrDefault(c,0)+1);//当出现重复字符,窗口收缩while(window.get(c) > 1){char d = s.charAt(left);left++;window.put(d,window.get(d)-1);}ans = Math.max(ans, right-left);}return ans;}
}
