滑動窗口首先按照類型分溅漾，可以分為定長窗口和變長窗口吃环。
定長窗口也就是說題目給出來的時候吠撮，你知道這個窗口的長度是固定的孝冒，一般會要求你返回每個這樣的窗口柬姚。我們只需要處理I,J 2根指針同時向后移一位。然后每次的位移過程里做的事是需要技巧的庄涡。
定長窗口典型題目有
Given an integer array A and a sliding window of size K, find the maximum value of each window as it slides from left to right.
Assumptions
The given array is not null and is not empty
K >= 1, K <= A.length
Examples
A = {1, 2, 3, 2, 4, 2, 1}, K = 3, the windows are {{1,2,3}, {2,3,2}, {3,2,4}, {2,4,2}, {4,2,1}},
and the maximum values of each K-sized sliding window are [3, 3, 4, 4, 4]
或者
Find all occurrence of anagrams of a given string s in a given string l. Return the list of starting indices.
Assumptions
s is not null or empty.
l is not null.
Examples
l = "abcbac", s = "ab", return [0, 3] since the substring with length 2 starting from index 0/3 are all anagrams of "ab" ("ab", "ba").
上面第一個題目的技巧是維護一個單調(diào)DEQUE量承，我們需要思考的是一個窗口里的最大值取決于什么，有哪些元素對最大值是完全沒有貢獻的啼染。我們發(fā)現(xiàn)宴合，一個位置靠前并且比這個窗口里后面的值還小的那個數(shù) 是不可能對之后窗口的最大值產(chǎn)生價值。所以我們可以之前把它丟掉迹鹅。根據(jù)這個原則卦洽。我們DEQUE的最左端是該窗口的最大值。同時DEQUE維持了單調(diào)遞減的特性斜棚。后面繼續(xù)保持這個特性即可阀蒂。
public List<Integer> maxWindows(int[] array, int k) {
// Write your solution here
Deque<Integer> dq = new ArrayDeque<>();
if (k > array.length) k = array.length;
for (int i = 0; i < k; i++) {
while (!dq.isEmpty() && array[i] > dq.peekLast()) dq.pollLast();
dq.offerLast(array[i]);
}
List<Integer> res = new ArrayList<>();
res.add(dq.peekFirst());
for (int i = k; i < array.length; i++) {
if (array[i - k] == dq.peekFirst()) dq.pollFirst();
while (!dq.isEmpty() && array[i] > dq.peekLast()) dq.pollLast();
dq.offerLast(array[i]);
res.add(dq.peekFirst());
}
return res;
}
第二道題，就是要看什么時候需要去更新CNT變量弟蚀，只有當(dāng)S里的字符的計數(shù)是正的時候蚤霞，刪除的時候需要CNT--。是》=0的時候义钉，增加的時候需要CNT++昧绣。 因為無用的字符，前面沒有初始化捶闸。所以增加的時候那時的值必然為負數(shù)夜畴。
public List<Integer> allAnagrams(String sh, String lo) {
int i = 0;
int[] map = new int[256];
for (char c : sh.toCharArray()) map[c]++;
int cnt = sh.length();
List<Integer> res = new ArrayList<>();
if (lo.length() < sh.length()) return res;
int j = 0;
while (j < sh.length()) {
if (map[lo.charAt(j++)]-- > 0){
cnt--;
}
}
if (cnt == 0) res.add(i);
while (j < lo.length()) {
if (map[lo.charAt(i++)]++ >= 0){
cnt++;
}
if (map[lo.charAt(j++)]-- > 0) {
cnt--;
}
if (cnt == 0) res.add(i);
}
return res;
}
其他定長窗口
Given a string containing only 'A', 'B', 'C', 'D', return the number of occurrences of substring which has length 4 and includes all of the characters from 'A', 'B', 'C', 'D' with in descending sorted order.
Assumptions:
The given string is not null and has length of >= 4.
In the output, if two substrings have the same frequency, then they should be sorted by the their natural order.
Examples:
“ABCDABCDD”, --> {"ABCD" : 2, "BCDA" : 1, "CDAB" : 1, "DABC" : 1}
/**
* public class Frequency {
* public String str;
* public int freq;
* public Frequency(String str, int freq) {
* this.str = str;
* this.freq = freq;
* }
* }
*/
public class Solution {
public List<Frequency> frequency(String input) {
Map<String,Integer> map = new HashMap<>();
int[] m = new int[4];
int i = 0;
int cnt = 0;
char[] cs = input.toCharArray();
for (; i < 4; i++) {
if(m[cs[i] - 'A']++ == 0) cnt++;
}
for (; i <= cs.length; i++) {
if (cnt == 4) {
String key = input.substring(i - 4, i);
map.putIfAbsent(key,0);
map.put(key, map.get(key) + 1);
}
if (i == cs.length) break;
if(--m[cs[i - 4] - 'A'] == 0) cnt--;
if(m[cs[i] - 'A']++ == 0) cnt++;
}
List<Frequency> res = new ArrayList<Frequency>();
for (String key : map.keySet()) {
res.add(new Frequency(key, map.get(key)));
}
Collections.sort(res, new Comparator<Frequency> () {
public int compare(Frequency a, Frequency b) {
if (a.freq == b.freq) return a.str.compareTo(b.str);
return b.freq - a.freq;
}
});
return res;
}
}
下面我們來看變長的窗口。
變長窗口最讓人頭疼的問題是很容易删壮，移著移著指針就混亂了贪绘，一跑代碼不是有錯誤，就是INDEX越界央碟。所以基于這個問題税灌，我設(shè)計了一套針對滑動窗口的不變量來避免寫代碼的時候發(fā)生想不清楚而引入BUG或者死循環(huán)指針越界的問題。
變長窗口會有2類 一般會讓你找最長的窗口亿虽，或者最短的窗口菱涤。所以道題滑動變長窗口題，可以僅僅改一個單詞洛勉，就讓題目變化狸窘。
比如：
Given a string, return the longest contiguous substring that contains exactly k type of characters.
Return null if there does not exist such substring.
Assumptions:
The given string is not null.
k >= 0.
Examples:
input = "aabcc", k = 3, output = "aabcc".
input = "aabcccc", k = 2, output = "bcccc".
變化：
Given a string, return the shortest contiguous substring that contains exactly k type of characters.
Return an empty string if there does not exist such substring.
Assumptions:
The given string is not null.
k >= 0.
Examples:
input = "aabcc", k = 3, output = "abc".
input = "aabbbcccc", k = 3, output = "abbbc".
input = "aabcc", k = 4, output = "".
如果求最長，也就是在窗口滿足條件的時候坯认，移動后面一個（J）指針翻擒。
如果求最短氓涣，則相反，當(dāng)窗口滿足條件時陋气，移動前一個（I）指針劳吠。
根據(jù)上述思想，我們要思考I,J的物理意義
我個人一般喜歡定義窗口區(qū)間為前閉巩趁，后開
這樣給I,J 賦初始值的時候可以為0,0
那么循環(huán)退出一般是J 》 ARRAY.LENGTH的時候
所以我一般會用如下框架解決滑動窗口痒玩。
先看找最小窗口
int min = Integer.MAX_VALUE;
int i = 0, j = 0;
while (j <= array.length) {
if (滿足條件) {
min = Math.min(min, j - i);
updateState(i++)
} else {
if (j == array.length) break;
updateState(j++)
}
}
return min;
最長窗口
int max= 0;
int i = 0, j = 0;
while (j <= array.length) {
if (窗口需要增大) {
if (滿足條件）
max= Math.max(max, j - i);
if (j == array.length) break;
updateState(j++)
} else {
updateState(i++)
}
}
return max;
根據(jù)這2個設(shè)計思路，我們可以很輕松的解決上面2個問題议慰。
public String shortest(String input, int k) {
char[] cs = input.toCharArray();
int min = cs.length;
int s = 0, e = 0;
int i = 0, j = 0;
int[] map = new int[256];
if (k == 0) return "";
while (j <= cs.length) {
if (k == 0) {
if (j - i < min) {
min = j - i;
s = i;
e = j;
}
if (++map[cs[i++]] == 0) k++;
} else {
if (j == cs.length) break;
if (map[cs[j++]]-- == 0) k--;
}
}
return input.substring(s,e);
}
最長
public String longest(String input, int k) {
char[] cs = input.toCharArray();
int max = 0;
int s = 0, e = 0;
int i = 0, j = 0;
int[] map = new int[256];
if (k == 0) return "";
while (j <= cs.length) {
if (k >= 0) {
if (k == 0 && j - i > max) {
max = j - i;
s = i;
e = j;
}
if (j == cs.length) break;
if (map[cs[j++]]-- == 0) k--;
} else {
if (++map[cs[i++]] == 0) k++;
}
}
return s == e ? null : input.substring(s,e);
}
我們再來看幾道別的題蠢古，是不是都差不多了。
Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T
Input: S = “ADOBECODEBANC”
T = “ABC”
Output: “BANC”
public String minWindow(String source, String target) {
int[] map = new int[256];
for (char c : target.toCharArray()) {
map[c]++;
}
int i = 0, j = 0;
char[] cs = source.toCharArray();
int cnt = target.length();
if (cnt == 0) return target;
int min = source.length();
int s = 0, e = 0;
while (j <= cs.length) {
if (cnt == 0) {
if (j - i < min) {
min = j - i;
s = i;
e = j;
}
if (map[cs[i++]]++ == 0) cnt++;
} else {
if (j == cs.length) break;
if (map[cs[j++]]-- > 0) cnt--;
}
}
return source.substring(s,e);
}
Smallest Substring Containing All Characters Of Another String
Given two strings s1 and s2, find the shortest substring in s1 containing all characters in s2.
If there does not exist such substring in s1, return an empty string.
Assumptions:
s1 and s2 are not null or empty.
Examples:
s1= “The given test strings”
s2: “itsst”
Output string: “st stri”
public String smallest(String s1, String s2) {
int[] map = new int[256];
for (char c : s2.toCharArray()) map[c]++;
int cnt = s2.length();
int i = 0, j = 0;
char[] cs = s1.toCharArray();
int min = Integer.MAX_VALUE, s = 0, e = 0;
while (j <= cs.length) {
if (cnt == 0) {
if (j - i < min) {
min = j - i;
s = i;
e = j;
}
if (++map[cs[i++]] > 0) cnt++;
} else{
if (j == cs.length) break;
if (map[cs[j++]]-- > 0) cnt--;
}
}
return s1.substring(s,e);
}
Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
public int minSubArrayLen(int num, int[] nums) {
int i = 0, j = 0, min = Integer.MAX_VALUE;
if (num <= 0) return 0;
while (j <= nums.length) {
if (num <= 0) {
min = Math.min(min, j - i);
num += nums[i++];
} else {
if (j == nums.length) break;
num -= nums[j++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
最長的變長窗口
Longest Substring with At Most Two Distinct Characters
Given a string, find the the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”, T is "ece"
public int lengthOfLongestSubstringTwoDistinct(String input) {
char[] cs = input.toCharArray();
int i = 0, j = 0;
int k = 2;
int[] map = new int[256];
int max = 0;
while (j <= cs.length) {
if (k >= 0) {
max = Math.max(max, j - i);
if (j == cs.length) break;
if (map[cs[j++]]++ == 0) k--;
} else {
if (--map[cs[i++]] == 0) k++;
}
}
return max;
}
