--刷題記錄--滑動視窗

滑動視窗記錄總結

• 滑動視窗
• • 大體架構
  • 可行技巧
  • 算法執行個體
  • • 尋找最靠左子串

用于自己刷題記錄

轉載自：https://blog.csdn.net/Dby_freedom/article/details/89066140

滑動視窗

滑動視窗是在一個小于原字元串或數組上進行操作，不在整個字元串和數組上操作，可以将一些嵌套循環變成一個單循環，減少時間複雜度。

一般用在數組和字元串中。

大體架構

滑動：視窗是移動的

視窗：視窗的大小可以是固定的，也可以不是固定，可以縮小也可擴容

思路：

1. 字元串S中設定雙指針，left = right =0，把[left, right]當成一個視窗
2. 不斷增加right指針，擴大視窗，直到視窗中字元串符合要求（包含另一個字元串的全部字元）—尋找可行解
3. 此時不增加right，增加左指針，縮小視窗，如果同時滿足要求，視窗大小小于最小的視窗，則更新左右區間，直到不滿足要求—優化可行解
4. 重複2和3，直到right到達字元串S的盡頭

可行技巧

包含子串：由于一般的題目字元的限定範圍一般就是26或者整個字元表128，是以設定一個定長數組，用來記錄每個字元出現的次數，增加右邊界，出現滿足題意的情況即可，在滿足的情況下更新答案并且縮小左邊界，直到右邊界走完整個字元串。

外加循環：一般的滑動視窗隻要判斷右節點是否小于給定數組的長度即可，但是對于數組裡是字元串的題目，可以考慮在外面加一層大小為數組元素長度的循環。

算法執行個體

• 尋找最靠左子串
• Leetcode 209. 長度最小的子數組
• Leetcode 1004. 最大連續1的個數 III
• Leetcode 3. 無重複字元的最長子串
• LeetCode 76. 最小覆寫子串
• LeetCode 567. 字元串的排列
• LeetCode 239. 滑動視窗最大值
• LeetCode 30. 串聯所有單詞的子串

尋找最靠左子串

題目描述：尋找一個字元串中包含另一個子串的，最靠左的子串左右位置

代碼示例:

#include <iostream>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

int bcnt[10],acnt[10];//分别記錄B，A中的每個字元出現的個數
string A,B;
const int INF = 0x3f3f3f3f;//定義一個無窮大值

bool check() //滿足條件的check函數
{
    for(int i = 0;i < 10;i++){
        if(acnt[i] < bcnt[i]) return false;//A的子串中的每個字元出現的次數都大于等于B
    }
    return true;
}

void solve(){

    cin >> A >> B;
    
    memset(bcnt,0,sizeof(bcnt));//初始化的定義非常重要
    memset(acnt,0,sizeof(acnt));//初始化的定義
    
    for(auto& i : B) bcnt[i -'0']++; //記錄B中每個字元出現的次數

    int minlen = INF, left = -1, right = -1;//定義傳回值，一開始預設為-1，-1傳回值
    int l = 0,r = 0;//[l,r)，起始左右位置全為0
    
    while(r < A.length())
    {
        //先處理A的子串還不包含B串所有字元的情況
        //右端點需要右移, r對應的資料值得數量++
        acnt[A[r++] - '0']++;

        //check成立,A的子串包含B的所有字元左端點右移
        while(check()){
            
            if(r - l < minlen){//如果此時成立的最小範圍長度小于目前的最小範圍長度，就更新結果
                minlen = r-l;
                left = l,right = r-1;
            }
           
            acnt[A[l++] - '0']--; //如果成立就嘗試更新結果，把左端點往右移動
        }       
    }

    printf("%d %d\n",left,right);
}

int main()
{
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}