模板

void slidingWindow(const string& s)
{
    int left = 0, right = 0;
    unordered_map<char, int> window;

    while (right < s.size()) {
        // 擴大窗口
        winodw.add(s[right]);
        right++;

        // 判斷窗口是否要收縮
        while (left < right && window needs shrink) {
            // 縮小窗口
            winodw.remove(s[left]);
            left++;
        }
    }
}

核心概念

  • 先透過擴大窗口來找到一個「可行解」
  • 然後透過縮小窗口來優化這個「可行解」，進而找到最優解

Tip

  • 區間為左閉右開 [left, right), 因為若為左閉右閉, 則 window 中初始會有一個元素（這不符合我們定義的初始 window 為空）, 故應為左閉右開。

應注意的部分

  • 何時移動 right 擴大窗口？窗口加入元素時，應該更新哪些變數？
  • 窗口何時暫停擴大，開始移動 left 縮小窗口？從窗口移出元素時，應該更新哪些變數？
  • 結果應該在擴大窗口還是縮小窗口的時候進行更新？

經典例題

一般

進階（不會也沒差）