LeetCode 滑動視窗（Sliding Window）類問題總結
導語
滑動視窗類問題是面試當中的高頻題，問題本身其實並不複雜，但是實現起來細節思考非常的多，想著想著可能因為變數變化，指標移動等等問題，導致程式反覆刪來改去，有思路，但是程式寫不出是這類問題最大的障礙。本文會將 LeetCode 裡面的大部分滑動視窗問題分析、總結、分類，並提供一個可以參考的模版，相信可以有效減少面試當中的演算法實現部分的不確定性。
題目概覽
滑動視窗這類問題一般需要用到雙指標來進行求解，另外一類比較特殊則是需要用到特定的資料結構，像是 sorted_map。後者有特定的題型，後面會列出來，但是，對於前者，題形變化非常的大，一般都是基於字串和陣列的，所以我們重點總結這種基於雙指標的滑動視窗問題。
題目問法大致有這幾種：
- 給兩個字串，一長一短，問其中短的是否在長的中滿足一定的條件存在，例如：
- 求長的的最短子串，該子串必須涵蓋短的的所有字元
- 短的的 anagram 在長的中出現的所有位置
- ...
- 給一個字串或者陣列，問這個字串的子串或者子陣列是否滿足一定的條件，例如：
- 含有少於 k 個不同字元的最長子串
- 所有字元都只出現一次的最長子串
- ...
除此之外，還有一些其他的問法，但是不變的是，這類題目脫離不開主串（主陣列）和子串（子陣列）的關係，要求的時間複雜度往往是，空間複雜度往往是常數級的。之所以是滑動視窗，是因為，遍歷的時候，兩個指標一前一後夾著的子串（子陣列）類似一個視窗，這個視窗大小和範圍會隨著前後指標的移動發生變化。
解題思路
根據前面的描述，滑動視窗就是這類題目的重點，換句話說，視窗的移動就是重點。我們要控制前後指標的移動來控制視窗，這樣的移動是有條件的，也就是要想清楚在什麼情況下移動，在什麼情況下保持不變，我在這裡講講我的想法，我的思路是保證右指標每次往前移動一格，每次移動都會有新的一個元素進入視窗，這時條件可能就會發生改變，然後根據當前條件來決定左指標是否移動，以及移動多少格。我寫來一個模版在這裡，可以參考：
public int slidingWindowTemplate(String[] a, ...) {
// 輸入引數有效性判斷
if (...) {
...
}
// 申請一個雜湊，用於記錄視窗中具體元素的個數情況
// 這裡用陣列的形式呈現，也可以考慮其他資料結構
int[] hash = new int[...];
// 預處理(可省), 一般情況是改變 hash
...
// l 表示左指標
// count 記錄當前的條件，具體根據題目要求來定義
// result 用來存放結果
int l = 0, count = ..., result = ...;
for (int r = 0; r < A.length; ++r) {
// 更新新元素在雜湊中的數量
hash[A[r]]--;
// 根據視窗的變更結果來改變條件值
if (hash[A[r]] == ...) {
count++;
}
// 如果當前條件不滿足，移動左指標直至條件滿足為止
while (count > K || ...) {
...
if (...) {
count--;
}
hash[A[l]]++;
l++;
}
// 更新結果
results = ...
}
return results;
}
複製程式碼
這裡面的 “移動左指標直至條件滿足” 部分，需要具體題目具體分析，其他部分的變化不大，我現在來看看具體的題目。
具體題目分析及程式碼
438. Find All Anagrams in a String
別看這是一道 easy 難度的題目，如果限定你在時間複雜度內實現呢？按照模版會很簡單，首先視窗是固定的，視窗長度就是輸入引數中第二個字串的長度，也就是說，右指標移動到某個位置後，左指標必須跟著一同移動，且每次移動都是一格，模版中 count 用來記錄視窗內滿足條件的元素，直到 count 和視窗長度相等即可更新答案
public List<Integer> findAnagrams(String s, String p) {
if (s.length() < p.length()) {
return new ArrayList<Integer>();
}
char[] sArr = s.toCharArray();
char[] pArr = p.toCharArray();
int[] hash = new int[26];
for (int i = 0; i < pArr.length; ++i) {
hash[pArr[i] - 'a']++;
}
List<Integer> results = new ArrayList<>();
int l = 0, count = 0, pLength = p.length();
for (int r = 0; r < sArr.length; ++r) {
hash[sArr[r] - 'a']--;
if (hash[sArr[r] - 'a'] >= 0) {
count++;
}
if (r > pLength - 1) {
hash[sArr[l] - 'a']++;
if (hash[sArr[l] - 'a'] > 0) {
count--;
}
l++;
}
if (count == pLength) {
results.add(l);
}
}
return results;
}
複製程式碼
同樣是兩個字串之間的關係問題，因為題目求的最小子串，也就是視窗的最小長度，說明這裡的視窗大小是可變的，這裡移動左指標的條件變成，只要左指標指向不需要的字元，就進行移動
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
char[] sArr = s.toCharArray();
char[] tArr = t.toCharArray();
int[] hash = new int[256];
for (int i = 0; i < tArr.length; ++i) {
hash[tArr[i]]++;
}
int l = 0, count = tArr.length, max = s.length() + 1;
String result = "";
for (int r = 0; r < sArr.length; ++r) {
hash[sArr[r]]--;
if (hash[sArr[r]] >= 0) {
count--;
}
while (l < r && hash[sArr[l]] < 0) {
hash[sArr[l]]++;
l++;
}
if (count == 0 && max > r - l + 1) {
max = r - l + 1;
result = s.substring(l, r + 1);
}
}
return result;
}
複製程式碼
159. Longest Substring with At Most Two Distinct Characters
這題視窗大小還是變化的，重點還是在何時更新左指標。這裡的 count 可以用來記錄當前有多少種不同的字元，只要當前進入視窗的字元使 count 不滿足題目條件，我們就移動左指標讓 count 滿足條件。這裡 result 初始化為 1，因為只要輸入的字串不是空的，視窗大小不可能小於 1。
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] sArr = s.toCharArray();
int[] hash = new int[256];
int l = 0, count = 0, result = 1;
for (int r = 0; r < sArr.length; ++r) {
hash[sArr[r]]++;
if (hash[sArr[r]] == 1) {
count++;
}
while (count > 2) {
hash[sArr[l]]--;
if (hash[sArr[l]] == 0) {
count--;
}
l++;
}
result = Math.max(result, r - l + 1);
}
return result;
}
複製程式碼
340. Longest Substring with At Most K Distinct Characters
和上題一樣，把 2 變成 k 即可
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) {
return 0;
}
char[] sArr = s.toCharArray();
int[] hash = new int[256];
int l = 0, count = 0, result = 1;
for (int r = 0; r < sArr.length; ++r) {
hash[sArr[r]]++;
if (hash[sArr[r]] == 1) {
count++;
}
while (count > k) {
hash[sArr[l]]--;
if (hash[sArr[l]] == 0) {
count--;
}
l++;
}
result = Math.max(result, r - l + 1);
}
return result;
}
複製程式碼
3. Longest Substring Without Repeating Characters
輸入只有一個字串，要求子串裡面不能夠有重複的元素，這裡 count 都不需要定義，直接判斷雜湊雜湊裡面的元素是不是在視窗內即可，是的話得移動左指標去重。
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] sArr = s.toCharArray();
int[] hash = new int[256];
int l = 0, result = 1;
for (int r = 0; r < sArr.length; ++r) {
hash[sArr[r]]++;
while (hash[sArr[r]] != 1) {
hash[sArr[l]]--;
l++;
}
result = Math.max(result, r - l + 1);
}
return result;
}
複製程式碼
和 438 那題很類似，但是這裡不需要記錄答案了，有就直接返回 true。
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
char[] s1Arr = s1.toCharArray();
char[] s2Arr = s2.toCharArray();
int[] hash = new int[26];
for (int i = 0; i < s1Arr.length; ++i) {
hash[s1Arr[i] - 'a']++;
}
int l = 0, count = 0;
for (int r = 0; r < s2Arr.length; ++r) {
hash[s2Arr[r] - 'a']--;
if (hash[s2Arr[r] - 'a'] >= 0) {
count++;
}
if (r >= s1Arr.length) {
hash[s2Arr[l] - 'a']++;
if (hash[s2Arr[l] - 'a'] >= 1) {
count--;
}
l++;
}
if (count == s1Arr.length) {
return true;
}
}
return false;
}
複製程式碼
992. Subarrays with K Different Integers
看完了字串型別的題目，這次來看看陣列型別的，題目中的 subarray 已經明確了這個題可以考慮用滑動視窗，這題比較 trick 的一個地方在於，這裡不是求最小值最大值，而是要你計數，但是如果每次僅僅加 1 的話又不太對，例如 A = [1,2,1,2,3], K = 2 這個例子，假如右指標移到 index 為 3 的位置，如果按之前的思路左指標根據 count 來移動，當前視窗是 [1,2,1,2] ，但是怎麼把 [2,1] 給考慮進去呢？可以從陣列和子陣列的關係來思考，假如 [1,2,1,2] 是符合條件的陣列，如果要計數的話， [1,2,1,2] 要求的結果是否和 [1,2,1] 的結果存在聯絡？這兩個陣列的區別在於多了一個新進來的元素，之前子陣列計數沒考慮到這個元素，假如把這個元素放到之前符合條件的子陣列中組成的新陣列也是符合條件的，我們看看這個例子中所有滿足條件的視窗以及對應的滿足條件的子陣列情況：
[1,2,1,2,3]// 視窗滿足條件 l r// 滿足條件的子陣列 [1,2] [1,2,1,2,3]// 視窗滿足條件 lr// 滿足條件的子陣列 [1,2],[2,1],[1,2,1] [1,2,1,2,3]// 視窗滿足條件 lr// 滿足條件的子陣列 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2] [1,2,1,2,3]// 視窗不滿足條件，移動左指標至滿足條件 lr [1,2,1,2,3]// 視窗滿足條件 l r// 滿足條件的子陣列 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2],[2,3] 複製程式碼
你可以看到對於一段連續的陣列，新的元素進來，視窗增加 1，每次的增量都會在前一次增量的基礎上加 1。當新的元素進來打破當前條件會使這個增量從新回到 1，這樣我們左指標移動條件就是隻要是移動不會改變條件，就移動，不然就停止
public int subarraysWithKDistinct(int[] A, int K) {
if (A == null || A.length < K) {
return 0;
}
int[] hash = new int[A.length + 1];
int l = 0, results = 0, count = 0, result = 1;
for (int r = 0; r < A.length; ++r) {
hash[A[r]]++;
if (hash[A[r]] == 1) {
count++;
}
while (hash[A[l]] > 1 || count > K) {
if (count > K) {
result = 1;
count--;
} else {
result++;
}
hash[A[l]]--;
l++;
}
if (count == K) {
results += result;
}
}
return results;
}
複製程式碼
424. Longest Repeating Character Replacement
這道題想 accept 的話不難，但是問題在於怎麼知道當前視窗中數量最多的字元的數量，因為需要替換的字元就是當前視窗的大小減去視窗中數量最多的字元的數量。最簡單的方法就是把雜湊雜湊遍歷一邊找到最大的字元數量，但是仔細想想如果我們每次新進元素都更新這個最大數量，且只更新一次，我們儲存的是當前遍歷過的全域性的最大值，它肯定是比實際的最大值大的，我們左指標移動的條件是 r - l + 1 - maxCount > k ，儲存的結果是 result = Math.max(r - l + 1, result); 這裡 maxCount 比實際偏大的話，雖然導致左指標不能移動，但是不會記錄當前的結果，所以最後的答案並不會受影響
public int characterReplacement(String s, int k) {
if (s == null || s.length() == 0) {
return 0;
}
char[] sArr = s.toCharArray();
int[] hash = new int[26];
int l = 0, maxCount = 0, result = 0;
for (int r = 0; r < sArr.length; ++r) {
hash[sArr[r] - 'A']++;
maxCount = Math.max(maxCount, hash[sArr[r] - 'A']);
while (r - l + 1 - maxCount > k) {
hash[sArr[l] - 'A']--;
l++;
}
result = Math.max(r - l + 1, result);
}
return result;
}
複製程式碼
其他題型
可以參考我之前寫的 Arts 的演算法部分 ->Arts 第三週
求中值的問題比較特殊，如果是亂序的情況下最好就是藉助堆，利用兩個堆，一個大頂，一個小頂，並且保證兩個堆記憶體放的數目相差不超過 1，這樣如果當前元素數目是偶數，兩個堆頂元素的均值就是結果，如果是奇數，存放元素多的那個堆的堆頂元素就是結果。
public double[] medianSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length < k ) {
return new double[0];
}
double[] results = new double[nums.length - k + 1];
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < nums.length; ++i) {
// add current element into queue
maxHeap.offer(nums[i]);
minHeap.offer(maxHeap.poll());
if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
// record answer
if (i >= k - 1) {
results[i - k + 1] = minHeap.size() < maxHeap.size()
? maxHeap.peek() : ((long)maxHeap.peek() + minHeap.peek()) * 0.5;
if (maxHeap.contains(nums[i - k + 1])) {
maxHeap.remove(nums[i - k + 1]);
} else {
minHeap.remove(nums[i - k + 1]);
}
}
}
return results;
}
複製程式碼
總結
雙指標類的滑動視窗問題思維複雜度並不高，但是出錯點往往在細節。記憶常用的解題模版還是很有必要的，特別是對於這種變數名多，容易混淆的題型。有了這個框架，思考的點就轉化為 “什麼條件下移動左指標”，無關資訊少了，思考加實現自然不是問題。