深入理解Sliding Window演算法

一、什麼是Sliding Window演算法

Sliding Window演算法是一種經典的雙指針演算法，通常用於處理數組和字元串的問題。Sliding Window演算法的核心思想是維護一個窗口，窗口大小可以動態調整，通過移動指針，更新窗口內容，從而得出問題的解。

Sliding Window演算法的時間複雜度通常為O(N)，空間複雜度為O(1)。

二、Sliding Window演算法的應用

Sliding Window演算法通常適用於以下場景：

1、找出滿足一定條件的最短/最長子串；

2、尋找連續子串，使得子串等於某個特定值或滿足某些條件；

3、找出所有滿足一定條件的子串。

三、Sliding Window演算法的實現

Sliding Window演算法通常需要定義左右指針，以及一個維護窗口信息的數據結構。具體實現方式可以分為以下幾步：

1、窗口初始化

定義左右指針，初始化之前先處理一些特殊情況。

return; // 特殊情況處理
int left = 0, right = 0; // 定義左右指針

2、移動右指針

根據題目要求，移動右指針並更新窗口內容，直到窗口不滿足要求。

while (right < n) {
    if (window needs to grow) {
        right++;
        update window;
    } else {
        break;
    }
}

3、移動左指針

窗口不滿足要求後，移動左指針並更新窗口內容，直到窗口重新滿足要求。

while (left <= right) {
    if (window needs to shrink) {
        update window;
        left++;
    } else {
        break;
    }
}

四、Sliding Window演算法的優化

Sliding Window演算法的時間複雜度通常為O(N)，但在實際應用中，可以通過一些技巧進一步優化。

1、用哈希表處理字元映射

如果處理的字元串包含字元映射，可以採用哈希表來快速查找。例如，給定字元串s和t，判斷s中是否包含t的排列之一：

bool check(string s, string t) {
    unordered_map needs, window;
    for (char c : t) needs[c]++;

    int left = 0, right = 0;
    int match = 0;

    while (right < s.size()) {
        char c1 = s[right];
        if (needs.count(c1)) {
            window[c1]++;
            if (window[c1] == needs[c1])
                match++;
        }
        right++;

        while (match == needs.size()) {
            if (window needs to shrink) {
                char c2 = s[left];
                if (needs.count(c2)) {
                    if (window[c2] == needs[c2])
                        match--;
                    window[c2]--;
                }
                left++;
            }

            // update result;
        }
    }

    // return result;
}

2、用滑動窗口處理數列問題

如果處理的是數列問題，可以採用滑動窗口技巧來處理。例如，給定一個序列和一個整數s，找出這個序列中符合條件的連續子序列的長度最小值：

int minSubArrayLen(int s, vector& nums) {
    int n = nums.size();
    int ans = INT_MAX;
    int left = 0, sum = 0;

    for (int right = 0; right = s) {
            ans = min(ans, right - left + 1);
            sum -= nums[left++];
        }
    }

    return ans == INT_MAX ? 0 : ans;
}

五、總結

Sliding Window演算法是一種高效的處理數組和字元串問題的演算法，核心思想是通過維護一個可調整大小的窗口，通過移動指針求解問題。在實際應用中，可以通過一些技巧進一步優化演算法性能。