---
tags: 演算法, LeetCode
disqus: HackMD
---

# 滑動視窗(Sliding Window)

## 介紹

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

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

有興趣了解可以參考[此影片](https://youtu.be/L6nroRENiAk)

### 滑動視窗演算法

(圖片取自[Sliding Window Algorithm](https://tealfeed.com/sliding-window-algorithm-r93tk))

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

## 練習

### 解題[3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

### 題目說明

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


### 解法一

#### 圖解


#### 程式碼:tada:

/**
 * @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`

#### 程式碼:tada:

/**
 * @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](https://leetcode.com/problems/permutation-in-string/)

## 特別感謝

感謝[Howard Gou](https://hackmd.io/@toto6038)大大訂正