寫程式

[LeetCode 核心演算法] Sliding Window 是什麼？最精簡解題技巧與常見題目

在這篇文章中，我介紹了滑動視窗（Sliding Window）這一常用於解決字串和陣列問題的演算法技巧。滑動視窗（Sliding Window）通過靈活調整子序列的起始和結束位置，以達到在線性時間內找到符合特定條件的最長或最短子序列的目的。此方法特別適合處理需要連續資料存取的情景，如數組、鏈表或字符串等。

Boison

2022年7月29日 • 2 min read

Photo by Marten Bjork / Unsplash

Sliding Window 通過不斷調整子序列的 start & end 位置，獲取滿足要求解

Sliding Window 可以算是廣義的左右指標中的一種，但是在某些情況下，Sliding Window 可以只使用一個 point 與一個 window size 來實作，並不用真正使用到兩個指標。

左右指標 (反向指標) 可見 Two Pointer: 低空間複雜度的解題技巧一文

一般來說若給定的資料是線性結構，例如 array, linked list 或 string 等可以循序存取 (sequential access)，而題目要求找出滿足特定條件的最長/最短的字串、陣列或一個目標值，常可以使用 Sliding Window。

圖片來源: Interview Guide Series — Sliding Window

Sliding Window 特性

在線性時間內完成
透過操控 two pointer 找出滿足條件的區間
不管是搜索的範圍或最終答案，一定都是 continuous 的資料，continuous 代表資料可以被依序存取

Sliding Window 常見題目

3. Longest Substring Without Repeating Characters

// BEST
function lengthOfLongestSubstring(s) {
    const set = new Set()
    let start = 0, length = 0
    for (let end = 0; end < s.length; end++) {
        while (set.has(s[end])) set.delete(s[start]), start++
        set.add(s[end])
        length = Math.max(length, set.size)
    }
    return length
}

lengthOfLongestSubstring('bbs') // 2
/*
end=0,set=[b  ],length=1
end=1,set=[   ],length=1
end=1,set=[b  ],length=1
end=2,set=[b,s],length=1
end=2,set=[b,s],length=2
*/

參考資料
1. Sliding Window – 陪你刷題
2. Two Pointer 與Sliding Window
3. Leetcode 刷題 pattern - Sliding Window
4. 滑動視窗（Sliding Window）演算法介紹
5. Reliable Transmission - Sliding Window Algorithm
6. 【演演算法】滑動視窗三步走
7. Leetcode 必备算法：聊聊滑动窗口

Sign up for more like this.