深入理解Sliding Window算法

OYPL • 2024-10-12 09:44 • 编程

一、什么是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算法是一种高效的处理数组和字符串问题的算法，核心思想是通过维护一个可调整大小的窗口，通过移动指针求解问题。在实际应用中，可以通过一些技巧进一步优化算法性能。

原创文章，作者：OYPL，如若转载，请注明出处：https://www.506064.com/n/142580.html