0.滑動(dòng)窗口原理講解

• 滑動(dòng)窗口：“同向雙指針”
• 滑動(dòng)窗口可處理「?段連續(xù)的區(qū)間」問(wèn)題
• 如何使用？
  1. left = 0, right = 0
  2. 進(jìn)窗口
  3. 判斷
     • 是否出窗口
  4. 更新結(jié)果 -> 視情況而定
     • 可能在出窗口前
     • 可能在進(jìn)窗口之后
• 具體原理解析將結(jié)合**「長(zhǎng)度最小的子數(shù)組」**來(lái)說(shuō)明

1.長(zhǎng)度最小的子數(shù)組

1.題目鏈接

• 長(zhǎng)度最小的子數(shù)組

2.算法原理講解

• 此問(wèn)題分析的對(duì)象是**「?段連續(xù)的區(qū)間」，因此可以考慮「滑動(dòng)窗?」**的思想來(lái)解決

• 讓滑動(dòng)窗?滿?：

  • 從i位置開(kāi)始，窗?內(nèi)所有元素的和?于target
  • 當(dāng)窗?內(nèi)元素之和第?次?于等于?標(biāo)值的時(shí)候，就是i位置開(kāi)始滿?條件的最??度

• 做法：

  • 如果窗?sum >= target：
    • 更新結(jié)果，并且將左端元素劃出去的同時(shí)繼續(xù)判斷是否滿?條件并更新結(jié)果
      • 因?yàn)樽蠖嗽乜赡芎?，劃出去之后依舊滿?條件
  • 如果窗?sum不滿?條件：
    • right++，讓下?個(gè)元素進(jìn)?窗?
      

• 為何滑動(dòng)窗?可以解決問(wèn)題，并且時(shí)間復(fù)雜度更低？

  • 這個(gè)窗?尋找的是：以當(dāng)前窗?最左側(cè)元素(記為left1)為基準(zhǔn)，符合條件的情況
    • 即：從left1開(kāi)始，滿?sum >= target時(shí)的最右側(cè)(記為right1)能到哪?
  • 既然已經(jīng)找到從left1開(kāi)始的最優(yōu)的區(qū)間，那么就可以?膽舍去left1
    • 但是如果繼續(xù)像暴力求解?法?樣，重新開(kāi)始統(tǒng)計(jì)第?個(gè)元素(left2)往后的和，勢(shì)必會(huì)有?量重復(fù)的計(jì)算
      • 因?yàn)樵谇蟮?段區(qū)間的時(shí)候，已經(jīng)算出很多元素的和了，這些和是可以在計(jì)算下次區(qū)間和的時(shí)候?上的
  • 此時(shí)，rigth1的作?就體現(xiàn)出來(lái)了，只需將left1這個(gè)值從sum中剔除
    • 從right1這個(gè)元素開(kāi)始，往后找滿?left2元素的區(qū)間
      • 此時(shí)right1也有可能是滿?的，因?yàn)?code>left1可能很?，sum剔除掉left1之后，依舊滿??于等于 target
  • 這樣就能省掉?量重復(fù)的計(jì)算
  • 總結(jié)：利用單調(diào)性，規(guī)避了很多沒(méi)有必要的枚舉行為
    • 此處的單調(diào)指滑動(dòng)窗口內(nèi)sum的單調(diào)性，而不是數(shù)組原始數(shù)據(jù)的單調(diào)性

• 時(shí)間復(fù)雜度：$O(N)$

  • 雖然代碼是兩層循環(huán)，但是left指針和right指針都是不回退的，兩者最多都往后移動(dòng)n次

3.代碼實(shí)現(xiàn)

int MinSubArrayLen(int target, vector<int>& nums) 
{int sum = 0, len = INT_MAX;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right]; // 進(jìn)窗口while(sum >= target) // 判斷{len = min(len, right - left + 1); // 更新結(jié)果sum -= nums[left++]; // 出窗口}}return len == INT_MAX ? 0 : len;
}