一丹弱、滑動窗口算法
也會使用兩個指針烂叔，但和雙指針算法不同的是雙指針算法關(guān)注的往往是兩個指針正在指向的兩個元素谨胞，而滑動窗口算法關(guān)注的是兩個指針之間的窗口，動態(tài)維護窗口中的信息蒜鸡。
滑動窗口算法一般用于解決子串或子數(shù)組問題胯努，碰到這兩種問題可以優(yōu)先考慮滑動窗口。
二术瓮、四個例子
leetcode 209. 長度最小的子數(shù)組
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組贰健。如果不存在符合條件的連續(xù)子數(shù)組胞四，返回 0。
示例:
輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數(shù)組 [4,3] 是該條件下的長度最小的連續(xù)子數(shù)組伶椿。
假如使用暴力求解：
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int minLen = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; ++i){
int sum = 0;
for(int j = i; j < nums.length; ++j){
sum += nums[j];
if(sum >= s){
minLen = Math.min(minLen, j-i+1);
break;
}
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}
每次從第 i 個元素開始向后累加辜伟，直到子數(shù)組和大于等于 s，然后更新最小長度脊另。
時間復雜度為 导狡。
使用滑動窗口求解：
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left = 0, right = 0;
int minLen = Integer.MAX_VALUE;
int winSum = 0;
while(right < nums.length){
winSum += nums[right];
right++;
while(winSum >= s){
minLen = Math.min(minLen, right-left);
winSum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}
窗口中維護一個 窗口子數(shù)組和 的信息（winSum），窗口每向右納入一個新元素（right 指針右移）偎痛，就檢查窗口的合法性旱捧，如果窗口合法，則更新最小窗口信息踩麦，并不斷從左邊移除窗口內(nèi)的元素（left 指針右移）枚赡，并同時檢查窗口合法性和更新最小窗口信息，直到窗口不合法谓谦。此時贫橙，再不斷向右納入新元素，直至窗口重新合法或算法結(jié)束反粥。
時間復雜度為 卢肃。
暴力解法每個元素都會被累加若干次疲迂，而滑動窗口每個元素至多累加累減一次，避免了大量的冗余計算莫湘。
如果我們理解了上述過程尤蒿，就可以總結(jié)出滑動窗口算法的偽碼框架：
while(right < nums.length){
window.add(nums[right]);
right++;
while(window 合法){ // 如果窗口合法，移動 left 縮小窗口
result = update(window); // 根據(jù)當前窗口逊脯，更新結(jié)果
window.remove(nums[left]);
left++;
}
}
return result;
leetcode 30. 串聯(lián)所有單詞的子串
給定一個字符串 s 和一些長度相同的單詞 words优质。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置。
注意子串要與 words 中的單詞完全匹配军洼，中間不能有其他字符巩螃，但不需要考慮 words 中單詞串聯(lián)的順序。
示例 1：
輸入：
s = "barfoothefoobarman",
words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoo" 和 "foobar" 匕争。
輸出的順序不重要, [9,0] 也是有效答案避乏。
示例 2：
輸入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
輸出：[]
滑動窗口解法：
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if(s.length() == 0 || words.length == 0) return result;
Map<String, Integer> countMap = new HashMap<>();
for(String w : words) countMap.put(w, countMap.getOrDefault(w, 0)+1);
Map<String, Integer> workMap = new HashMap<>(); // 維護窗口中的單詞
int wordLen = words[0].length();
int wordsLen = words.length*wordLen;
for(int i = 0; i < wordLen; ++i){ // 錯位遍歷，保證所有情況都遍歷到
workMap.clear();
int left = i, right = i;
while(right <= s.length()-wordLen){
String rw = s.substring(right, right+wordLen);
workMap.put(rw, workMap.getOrDefault(rw, 0)+1);
right += wordLen;
if(!countMap.containsKey(rw)){ // 重置窗口
left = right;
workMap.clear();
continue;
}
while(workMap.get(rw) > countMap.get(rw)){ // 刪除左邊單詞甘桑，使窗口合法
String lw = s.substring(left, left+wordLen);
workMap.put(lw, workMap.get(lw)-1);
left += wordLen;
}
if(right-left == wordsLen) result.add(left);
}
}
return result;
}
}
對應的滑動窗口偽碼框架為：
while(right 沒有越界){
window.add(rightWord);
right 右移;
if(window 不合法 && 不能通過移動 left 使 window 合法){
重置窗口;
continue;
}
while(window 不合法){
window.remove(leftWord);
left 右移;
}
if(window 符合要求) result = update(window);
}
每次先往窗口里添加一個新單詞拍皮，通過 HashMap 判斷添加的單詞是否合法，如果新單詞根本不在 words 里面跑杭，那當前窗口就全部不可用了铆帽，重置窗口，將 left 設為 right德谅，重新匹配爹橱。如果新單詞在 words 里，但新單詞在窗口里的出現(xiàn)次數(shù)大于在 words 里的出現(xiàn)次數(shù)窄做，通過移動 left 指針愧驱，不斷刪除窗口左端的單詞，直至窗口重新合法椭盏，如果 words 里的所有單詞都在窗口中组砚，就可以更新結(jié)果集了。
和上一個例子不同的是掏颊，這里 left 右移是為了使窗口重新合法糟红，而上一個例子是為了使窗口重新不合法，所以兩者結(jié)果集的更新時機不同乌叶。
leetcode 438. 找到字符串中所有字母異位詞
給定一個字符串 s 和一個非空字符串 p改化，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引枉昏。
字符串只包含小寫英文字母陈肛，并且字符串 s 和 p 的長度都不超過 20100。
說明：
- 字母異位詞指字母相同兄裂，但排列不同的字符串句旱。
- 不考慮答案輸出的順序阳藻。
示例 1:
輸入:
s: "cbaebabacd" p: "abc"
輸出:
[0, 6]
解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞谈撒。
示例 2:
輸入:
s: "abab" p: "ab"
輸出:
[0, 1, 2]
解釋:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母異位詞腥泥。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母異位詞。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母異位詞蛔外。
滑動窗口解法：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if(s.length() == 0) return result;
int[] map = new int[26];
for(char c : p.toCharArray()) ++map[c-'a'];
char[] ss = s.toCharArray();
int[] workMap = new int[26];
int left = 0, right = 0;
while(right < ss.length){
int rc = ss[right]-'a';
++workMap[rc];
right++;
if(map[rc] == 0){ // 重置窗口
while(left < right) --workMap[ss[left++]-'a']; // 移除窗口中的全部元素
continue;
}
while(workMap[rc] > map[rc]){ // 重新使窗口合法
--workMap[ss[left]-'a'];
left++;
}
if(right-left == p.length()) result.add(left);
}
return result;
}
}
這個例子和上一個很相似，只是基本單元不同溯乒，上一個例子的基本單元是字符串夹厌，而這個是字符。
為什么不像上一個例子一樣裆悄，直接調(diào)用 Arrays.fill(map, 0) 來重置窗口呢矛纹？
因為對上一個例子來說字符串的 substring()、hashCode() 和 equals() 操作比較費時光稼，不如直接 clear()或南。而這個例子相對來說直接 Arrays.fill() 更費時，因為會重置許多無關(guān)元素艾君。
leetcode 76. 最小覆蓋子串
給你一個字符串 S采够、一個字符串 T，請在字符串 S 里面找出：包含 T 所有字母的最小子串冰垄。
示例：
輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"
說明：
- 如果 S 中不存這樣的子串蹬癌，則返回空字符串 ""。
- 如果 S 中存在這樣的子串播演，我們保證它是唯一的答案冀瓦。
滑動窗口解法：
class Solution {
public String minWindow(String s, String t) {
int[] map = new int[128];
for(char c : t.toCharArray()) ++map[c];
char[] ss = s.toCharArray();
int start = -1, len = Integer.MAX_VALUE;
int left = 0, right = 0, count = 0;
while(right < ss.length){
if(map[ss[right]]-- > 0) ++count; // count 用來統(tǒng)計在窗口中的有效字符
right++;
while(count == t.length()){ // 移動 left 使窗口重新不合法
if(right-left < len){ // 更新結(jié)果
len = right-left;
start = left;
}
if(++map[ss[left]] > 0) --count;
left++;
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
}
}
只用到了一個 map伴奥，空間利用率很高写烤，只是稍微難理解一點。
map 本來只用于統(tǒng)計 t 字符串拾徙，但這里在窗口滑動的過程中直接修改了 map 的計數(shù)洲炊。我們可以將 if(map[ss[right]]-- > 0) ++count; 簡單理解為把 map 中的 t 的有效字符借到窗口中來，if(++map[ss[left]] > 0) --count; 理解為把 t 的有效字符從窗口中還回 map尼啡。
最小覆蓋子串問題其實是一種子串包含問題的泛化暂衡，前面的 串聯(lián)所有單詞的子串 和 找到字符串中所有字母異位詞 都屬于這種子串包含問題。我們同樣可以只用一個 map 來解決崖瞭。
串聯(lián)所有單詞的子串：
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if(s.length() == 0 || words.length == 0) return result;
Map<String, Integer> countMap = new HashMap<>();
int wordLen = words[0].length();
int wordsLen = words.length*wordLen;
for(int i = 0; i < wordLen; ++i){ // 錯位遍歷狂巢，保證所有情況都遍歷到
countMap.clear();
for(String w : words) countMap.put(w, countMap.getOrDefault(w, 0)+1);
int left = i, right = i, count = 0, val;
while(right+wordLen <= s.length()){
String rw = s.substring(right, right+wordLen);
countMap.put(rw, (val = countMap.getOrDefault(rw, 0))-1);
if(val > 0) ++count; // 有效單詞被放入窗口
right += wordLen;
while(count == words.length){
if(right-left == wordsLen) result.add(left);
String lw = s.substring(left, left+wordLen);
countMap.put(lw, val = countMap.get(lw)+1);
if(val > 0) --count; // 有效單詞被移出窗口
left += wordLen;
}
}
}
return result;
}
}
找到字符串中所有字母異位詞：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if(s.length() == 0) return result;
int[] map = new int[26];
for(char c : p.toCharArray()) ++map[c-'a'];
char[] ss = s.toCharArray();
int left = 0, right = 0, count = 0;
while(right < ss.length){
if(map[ss[right]-'a']-- > 0) ++count;
right++;
while(count == p.length()){ // 重新使窗口不合法
if(right-left == count) result.add(left);
if(++map[ss[left]-'a'] > 0) --count;
left++;
}
}
return result;
}
}
三、滑動窗口算法框架
通過上面四道題书聚，我們可以總結(jié)出常見的滑動窗口算法框架：
int left = 0, right = 0;
while(right < s.length){
window.add(s[right]);
right++;
while(valid){
window.remove(s[left]);
left++;
}
}
其中 window 維護的數(shù)據(jù)類型視題目而定唧领，可能就是一個變量也可能是一個哈希表或數(shù)組藻雌。
稍微麻煩的地方就是這個 valid 條件，為了實現(xiàn)這個條件的實時更新斩个，我們可能會寫很多代碼胯杭。比如前面的題目，看起來解法篇幅那么長受啥，實際上思想還是很簡單做个，只是大多數(shù)代碼都在處理這個問題而已。
