0.滑動窗口原理講解

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

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

1.題目鏈接

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

2.算法原理講解

• 此問題分析的對象是**「?段連續(xù)的區(qū)間」，因此可以考慮「滑動窗?」**的思想來解決

• 讓滑動窗?滿?：

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

• 做法：

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

• 為何滑動窗?可以解決問題，并且時間復(fù)雜度更低？

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

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

  • 雖然代碼是兩層循環(huán)，但是left指針和right指針都是不回退的，兩者最多都往后移動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;
}