前言
滑動視窗是雙指標的一種特例，可以稱為左右指標，在任意時刻，只有一個指標運動，而另一個保持靜止，滑動視窗路一般用于解決特定的序列中符合條件的連續的子序列的問題， 好處：時間復雜度 O(n^2) ---> O(n)一、演算法應用場景
關鍵詞：
1.滿足XXX條件（計算結果、出現次數、同時包含） 2.最長/最短/或最值 3.子串/子陣列/子序列 最最最重要的提示點是：必須是連續的，否則不可以用滑動視窗二、滑動視窗代碼模板
說明：理論上你可以設計兩端都開或者兩端都閉的區間，但設計為左閉右開區間是最方便處理的，因為這樣初始化 left = right = 0 時區間 [0, 0) 中沒有元素，但只要讓 right 向右移動（擴大）一位，區間 [0, 1) 就包含一個元素 0 了，如果你設定為兩端都開的區間，那么讓 right 向右移動一位后開區間 (0, 1) 仍然沒有元素；如果你設定為兩端都閉的區間，那么初始區間 [0, 0] 就包含了一個元素，這兩種情況都會給邊界處理帶來不必要的麻煩，
給出了兩個滑動視窗的模板，并且又給出了求最長/最短/固定時的模板，并不是說有五個模板，其實后三個模板是嵌套在前兩個中的，即后三個模板需要關注的是內層while的條件（視窗固定情況下時也可用while，但是if即可滿足）以及最終結果result的更新位置，
希望你寫滑動視窗時能有三問：
1、什么時候應該擴大視窗？
2、什么時候應該縮小視窗？
3、什么時候應該更新答案？
滑動視窗 + 變數計數模板
class Solution { public int slidingWindow(int[] nums, int k) { //陣列/字串長度 int n = nums.length; //雙指標，表示當前遍歷的區間[left, right），左閉右開 int left = 0, right = 0; //定義變數統計 子陣列/子區間 是否有效 int sum = 0; //定義變數動態保存最大 求和/計數 int res = 0; //右指標遍歷到陣列尾 while (right < n) { //增加當前右指標對應的數值 sum += nums[right]; //增加視窗，移動右指標，實作右開效果 right++； //當在該區間內 sum 超出定義范圍 while (sum > k) { //先將左指標指向的數值減去 sum -= nums[left]; //縮小視窗 left++; } //到 while 結束時，我們找到了一個符合題意要求的 子陣列/子串 res = Math.max(res, right - left); } return res; } }
滑動視窗 + 哈希表存盤模板
class Solution { public String slidingWindow(String s, String t) { //創建兩個哈希表，分別記錄 [視窗] 和 [需要的] Map<Character, Integer> window= new HashMap<>(); Map<Character, Integer> need= new HashMap<>(); //創建 [雙指標] 和 [有效數量] int left = 0, right = 0; int valid = 0; //外層回圈，供右指標遍歷 while(right < s.length()){ //創建臨時 c 字符，是移入 視窗 內的字符 char c = s.charAt(right); //增大視窗 right++; //進行視窗一系列邏輯更新 ... /*** debug 輸出的位置 ***/ //System.out.println("window: [" + left + "," + right + ")"); //判斷左指標是否要右移即視窗收縮：有效數量足夠滿足條件 /* 可能是規定的視窗大小超出了，可能是有效值數量達成了 1. while(valid == need.size()) 2. while(right - left >= s1.length()) */ while(windows need shrink){ // 創建 d 是要移除視窗的字符 char d = s.charAt(left); //縮小視窗 left++; //進行視窗一系列邏輯更新 ... } } } }
尋找最長模板（while為視窗不滿足條件，結果result在外部更新）
初始化 left，right，window，result
while("右指標沒有到結尾"){
視窗擴大，加入right對應元素，更新當前window
right++;(right右移，起到左閉右開的效果，[left,right))
while("window不滿足要求"){
視窗縮小，移除left對應元素，left右移
}
更新最優結果result
}
回傳result
尋找最短模板（while為視窗滿足條件，結果result在內部更新）
初始化 left，right，window，result
while("右指標沒有到結尾"){
視窗擴大，加入right對應元素，更新當前window
right++;(right右移，起到左閉右開的效果，[left,right))
while("window滿足要求"){
更新最優結果result
視窗縮小，移除left對應元素，left右移
}
}
回傳result
視窗大小固定模板
初始化 left，right，window，result while("右指標沒有到結尾"){ 視窗擴大，加入right對應元素，更新當前window right++;(right右移，起到左閉右開的效果，[left,right)) if("window達到固定值（right-left==target_length）"){ if(滿足條件){ 處理結果； } 視窗縮小，移除left對應元素，left右移 } } 回傳result
我偏要勉強!
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548811.html
標籤：其他
上一篇：知乎使用指南