<center id="qkqgy"><optgroup id="qkqgy"></optgroup></center>
  • <menu id="qkqgy"></menu>
    <nav id="qkqgy"></nav>
    <xmp id="qkqgy"><nav id="qkqgy"></nav>
  • <xmp id="qkqgy"><menu id="qkqgy"></menu>
    <menu id="qkqgy"><menu id="qkqgy"></menu></menu>
    <tt id="qkqgy"><tt id="qkqgy"></tt></tt>


  • ?此題用到的方法是滑動窗口(唬人叫法)

    但其實滑動窗口并不難,本質上還是雙指針,只不過換了一個馬甲而已,我們定義一個fast指針,一個slow指針,不斷的計算從slow指針到fast指針之間的值

    我們以力扣給出的示例作解釋

    我們令fast指針?=0;令slow指針=0

    再定義一個計算? 從slow指針到fast指針的總和的? int變量sum

    以及用來統計符合要求的連續子數組長度的count變量

    此時sum的值=2,小于target值?,我們就移動fast指針來擴大sum的值。

    ?此時sum的值=5,小于target的值,繼續移動fast指針來擴大sum的值,依次類推,我們發現當fast指向第四個元素?
    2??的時候,下標值等于7,記錄此時的數組長度count

    ?此時我們再次移動fast指針

    此時我們發現sum的值已經大于7了,那么這個時候我們就移動slow指針向前

    ?此時sum的值仍然大于7,我們就繼續移動slow指針

    ?我們發現此次sum的值又符合條件,就判斷此時的數組長度是否小于之前的count,如果小于就更新count的值。

    ?

    依次類推,終止條件為slow指針指向最后一個數組元素的時候。我們就能夠遍歷完整個數組,找出所有滿足我們sum等于target的連續子數組。

    這個題的思路為利用動態窗口統計出所有符合要求的連續子數組,獲取他的長度(我們這里的方法是fast指針-slow指針+1
    ),然后不斷與之前的count值進行比較,如果小于就更新,最終遍歷結束之后返回count就可以了

    以下為該題的實現

    int?minSubArrayLen(int?target,?int*?nums,?int?numsSize){

    ????//暴力寫法會超時,因此我們學習滑動窗口寫法,本質上還是雙指針。

    ? ??

    ????int fast=0;

    ????int slow=0;

    ????int?min=1000000;//用來存儲更新之后的最小長度

    ????int?sum=0;

    ???while(fast<numsSize)

    ????{

    ????????sum=sum+nums[fast];

    ????????while(sum>=target)

    ????????{

    ????????????int?count=fast-slow+1;//計算當前長度

    ????????????if(min>count)

    ????????????{

    ????????????????min=count;

    ????????????}

    ????????????sum-=nums[left++];

    ????????}

    ? ? ? ? fast++;

    ????????

    ????}

    ???if(min==1000000)//如果沒有滿足條件的子字符串

    ???{

    ???????return?0;

    ???}

    ???return?min;

    }

    總結:

    1.動態窗口可以實現快速的處理連續的數據。

    2.動態窗口有兩種:

    ? ?1.長度變換的動態窗口,也就是我們這種。

    ? ?2.長度不變換的動態窗口。

    3.什么情況可以用滑動窗口來解決實際問題呢?

    * 一般給出的數據結構是數組或者字符串
    * 求取某個子串或者子序列最長最短等最值問題或者求某個目標值時
    * 該問題本身可以通過暴力求解

    結束!

    ?

    技術
    下載桌面版
    GitHub
    百度網盤(提取碼:draw)
    Gitee
    云服務器優惠
    阿里云優惠券
    騰訊云優惠券
    華為云優惠券
    站點信息
    問題反饋
    郵箱:ixiaoyang8@qq.com
    QQ群:766591547
    關注微信
    巨胸美乳无码人妻视频