滑動視窗(Sliding Window)

介紹

滑動視窗協定

有學過計概都知道Sliding window protocol(滑動視窗協定)，Stop and Wait 一次只能傳一個封包，而 Sliding Window 則可以一次傳送一批封包，使用滑動窗口方法可以避免網路上的流量壅塞。由於傳送方(Sender)和接收方(Receiver)的 TCP 實作了封包緩衝區的滑動窗口，應用層仍將提供資料以傳輸到 TCP，而不必擔心網路流量壅塞問題。

窗口大小可能會根據網路流量動態變化，如果在通訊路徑的錯誤非常少，則可增加窗口的大小，以增加資料吞吐量。反之，則減少窗口的大小，以確保資料完整性而且維持吞吐量。

有興趣了解可以參考此影片

滑動視窗演算法

(圖片取自Sliding Window Algorithm)

那回到滑動視窗演算法，也是差不多的概念，透過使用一個可變的視窗大小或固定視窗大小來解題，通常多用在字串或陣列的問題，當然這有些題目可以透過暴力解法解決，但使用滑動視窗演算法可將時間複雜度從

$O(n^2)$或

$O(n^3)$降到

$O(n)$。

練習

解題3. Longest Substring Without Repeating Characters

題目說明

給予一個字串，找出不重複字串最長長度

解法一

圖解

程式碼

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let maxLength = 0;
    const unique = [];
    for (let char in [...s]) {
        while (unique.includes(s[char])){
            unique.shift();
        }
        unique.push(s[char]);
        maxLength = Math.max(unique.length, maxLength)
    }
    return maxLength;
};

解法二

使用一個集合(Set)來儲存目前子字串中的字元，並使用兩個指標 i 來 j 來追蹤子字串的開始和結束。只要目前的字元 arr[j] 不在集合中， arr[i] 向前移動指標，當找到不重複字元時 j 指標向前移動。

每當將新字元加入到集合中時，含有不重複字元的最長子字串的長度將更新為j - i

程式碼

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let set = new Set();
    let maxLength = 0;
    let i = 0;
    let j = 0;

    while (i < s.length && j < s.length) {
        if (!set.has(s[j])) {
            set.add(s[j++]);
            maxLength = Math.max(maxLength, j - i);
        } else {
            set.delete(s[i++]);
        }
    }

    return maxLength;
};

相似題

567. Permutation in String

特別感謝

感謝Howard Gou大大訂正