滑動視窗

簡介

#

滑動窗口（Sliding Window）是雙指針中的一種技巧，通常可以用來解決有單調性的連續子序列問題。

我們一樣會使用兩個指針，一個指向窗口的左端，另一個指向窗口的右端，然後根據題目的要求，我們會持續進行窗口的伸縮或移動。

例題

#

你有一個包含 \(n\) 個正整數的陣列，請找出最長的連續子序列，使得這個子序列的和不超過 \(s\)。

\(1 \leq n \leq 10^5\)

首先，你可以先試著用最暴力的作法解決這個問題：

for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
        // 現在我們要找出 l 和 r 之間的和
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum += nums[i];
        }
        // 更新答案
        if (sum <= s) {
            ans = max(ans, r - l + 1);
        }
    }
}

但是這個作法的時間複雜度是 \(O(n^3)\)，對於 \(n = 10^5\) 的情況，這個作法是不可接受的。

不過我們可以從中觀察到一個性質，就是當我們知道當前區間的值超過 \(s\) 時，無論如何都不能再擴大了，因為再怎麼擴大，區間的和只會更大。

這個單調性就是我們可以利用滑動視窗的原因，滑動窗口的題目通常都符合這樣的性質：「當我們知道當前區間的值不符合要求時，更大/更小的區間一定也不符合」。

一開始，我們的區間長這樣，沒有包含任何元素，也就是 \(l = r = 0\)：

接著嘗試擴大窗口，我們把右指針往右移動，發現目前區間的和還是小於 \(s\)：

再擴大：

一直擴大到這邊的時候，可以發現區間和還沒超過 \(s\)，我們現在的最大的區間長度是 \(4\)：

再擴大一次之後，我們發現區間的和已經超過 \(s\) 了：

這時候我們就要縮小窗口，把左指針往右移動：

區間和又小於 \(s\) 了，讓我們再擴大：

總之，我們會持續重複這個動作直到跑完整個陣列，這個邏輯簡單來說就是：

• 當區間和小於 \(s\) 時，我們就嘗試擴大窗口（右指針往右移動）
• 當區間和大於 \(s\) 時，我們就嘗試縮小窗口（左指針往右移動）

應該很容易估計時間複雜度是 \(O(n)\)，雖然有兩層迴圈，但是每個元素最多只會被訪問一次，所以根據均攤分析，這個作法的時間複雜度是 \(O(n)\)。

int sum = 0;

for (int l = 0, r = 0; r < n; r++) {
    // 現在我要找出 l 和 r 之間的和
    sum += nums[r];
    // 如果 sum 超過 s，我們就要縮小窗口
    while (sum > s) {
        sum -= nums[l];
        l++;
    }
    // 更新答案
    ans = max(ans, r - l + 1);
}