Skip to content

Latest commit

 

History

History
298 lines (199 loc) · 11.1 KB

01.Array-Sliding-Window.md

File metadata and controls

298 lines (199 loc) · 11.1 KB
Raw

1. 滑动窗口算法介绍

在计算机网络中，滑动窗口协议（Sliding Window Protocol）是传输层进行流控的一种措施，接收方通过通告发送方自己的窗口大小，从而控制发送方的发送速度，从而达到防止发送方发送速度过快而导致自己被淹没的目的。我们所要讲解的滑动窗口算法也是利用了同样的特性。

滑动窗口（Sliding Window）：在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

  • 滑动操作：窗口可按照一定方向进行移动。最常见的是向右侧移动。
  • 缩放操作：对于不定长度的窗口，可以从左侧缩小窗口长度，也可以从右侧增大窗口长度。

滑动窗口利用了双指针中的快慢指针技巧，我们可以将滑动窗口看做是快慢指针两个指针中间的区间，也可以可以将滑动窗口看做是快慢指针的一种特殊形式。

2. 滑动窗口适用范围

滑动窗口算法一般用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。该算法可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

根据问题，我们可以将滑动窗口分为以下两种：

  • 固定长度窗口：窗口大小是固定的。
  • 不定长度窗口：窗口大小是不固定的。
    • 求解最大的满足条件的窗口。
    • 求解最小的满足条件的窗口。

下面来分别讲解一下这两种类型题目。

3. 固定长度窗口

3.1 固定长度窗口求解步骤

假设窗口的固定大小为 window_size。

  1. 使用两个指针 left、right。初始时，left 、right 都指向序列的第一个元素，即：left = 0，right = 0 ，区间 [left, right] 被称为一个「窗口」。
  2. 当窗口未达到 window_size 大小时，不断移动 right，先将 window_size 个元素填入窗口中。
  3. 当窗口达到 window_size 大小时，判断窗口内的连续元素是否满足题目限定的条件。
    1. 如果满足，再根据要求更新最优解。
    2. 然后向右移动 left，从而缩小窗口长度，即 left += 1，使得窗口大小始终保持为 window_size。
  4. 向右移动 right，将元素填入窗口中。
  5. 重复 2 ~ 4 步，直到 right 到达序列末尾。

3.2 固定长度窗口模板

left = 0
right = 0

while right < len(nums):
    window.append(nums[right])
    
    # 超过窗口大小时，缩小窗口，维护窗口中始终为 window_size 的长度
    if right - left + 1 >= window_size:
        # ... 维护答案
        window.popleft()
        left += 1
    
    # 向右侧增大窗口
    right += 1

下面我们根据具体例子来讲解一下如何使用固定窗口大小的滑动窗口来解决问题。

3.3 大小为 K 且平均值大于等于阈值的子数组数目

3.3.1 题目链接

3.3.2 题目大意

给你一个整数数组 arr 和两个整数 k 和 threshold 。

要求：返回长度为 k 且平均值大于等于 threshold 的子数组数目。

3.3.3 解题思路

这道题目是典型的固定窗口大小的滑动窗口题目。窗口大小为 k。具体做法如下：

  1. ans 用来维护答案数目。window_sum 用来维护窗口中元素的和。
  2. left 、right 都指向序列的第一个元素，即：left = 0，right = 0。
  3. 当窗口元素个数不足 k 个时，不断移动 right，先将 k 个元素填入窗口中。
  4. 当窗口元素个数为 k 时，即：right - left + 1 >= k 时，判断窗口内的元素和平均值是否大于等于阈值。
    1. 如果满足，则答案数目 + 1。
    2. 然后向右移动 left，从而缩小窗口长度，即 left += 1，使得窗口大小始终保持为 k。
  5. 向右移动 right，将元素填入窗口中。
  6. 重复 3 ~ 5 步，直到 right 到达数组末尾。

最后输出答案数目。

3.3.4 代码

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        left = 0
        right = 0
        window_sum = 0
        ans = 0

        while right < len(arr):
            window_sum += arr[right]
            
            if right - left + 1 >= k:
                if window_sum >= k * threshold:
                    ans += 1
                window_sum -= arr[left]
                left += 1

            right += 1

        return ans

4. 不定长度窗口

4.1 不定长度窗口求解步骤

  1. 使用两个指针 left、right。初始时，left、right 都指向序列的第一个元素。即：left = 0，right = 0，区间 [left, right] 被称为一个「窗口」。
  2. 将区间最右侧元素添加入窗口中，即 window.add(s[right])。
  3. 然后向右移动 right，从而增大窗口长度，即 right += 1。直到窗口中的连续元素满足要求。
  4. 此时，停止增加窗口大小。转向不断将左侧元素移出窗口，即 window.popleft(s[left])。
  5. 然后向右移动 left，从而缩小窗口长度，即 left += 1。直到窗口中的连续元素不再满足要求。
  6. 重复 2 ~ 5 步，直到 right 到达序列末尾。

4.2 不定长度窗口模板

left = 0
right = 0

while right < len(nums):
    window.append(nums[right])
    
    while 窗口需要缩小:
        # ... 可维护答案
        window.popleft()
        left += 1
    
    # 向右侧增大窗口
    right += 1

4.3 无重复字符的最长子串

4.3.1 题目链接

4.3.2 题目大意

给定一个字符串 s。

要求：找出其中不含有重复字符的 最长子串 的长度。

4.3.3 解题思路

用滑动窗口 window 来记录不重复的字符个数，window 为哈希表类型。

设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口中没有重复字符。

  • 一开始，left、right 都指向 0。
  • 将最右侧字符 s[right] 加入当前窗口 window 中，记录该字符个数。
  • 如果该窗口中该字符的个数多于 1 个，即 window[s[right]] > 1，则不断右移 left，缩小滑动窗口长度，并更新窗口中对应字符的个数，直到 window[s[right]] <= 1。
  • 维护更新无重复字符的最长子串长度。然后右移 right，直到 right >= len(nums) 结束。
  • 输出无重复字符的最长子串长度。

4.3.4 代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        window = dict()
        ans = 0

        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1

            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1

            ans = max(ans, right - left + 1)
            right += 1

        return ans

4.4 长度最小的子数组

4.4.1 题目链接

4.4.2 题目大意

给定一个只包含正整数的数组 nums 和一个正整数 target。

要求：找出数组中满足和大于等于 target 的长度最小的「连续子数组」，并返回其长度。如果不存在符合条件的子数组，返回 0。

4.4.3 解题思路

最直接的做法是暴力枚举，时间复杂度为 $O(n^2)$。但是我们可以利用滑动窗口的方法，在时间复杂度为 $O(n)$ 的范围内解决问题。

用滑动窗口来记录连续子数组的和，设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口中的和刚好大于等于 target。

  • 一开始，left、right 都指向 0。
  • 向右移动 right，将最右侧元素加入当前窗口和 window_sum 中。
  • 如果 window_sum >= target，则不断右移 left，缩小滑动窗口长度，并更新窗口和的最小值，直到 window_sum < target。
  • 然后继续右移 right，直到 right >= len(nums) 结束。
  • 输出窗口和的最小值作为答案。

4.4.4 代码

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        size = len(nums)
        ans = size + 1
        left = 0
        right = 0
        window_sum = 0

        while right < size:
            window_sum += nums[right]

            while window_sum >= target:
                ans = min(ans, right - left + 1)
                window_sum -= nums[left]
                left += 1

            right += 1

        return ans if ans != size + 1 else 0

4.5 乘积小于K的子数组

4.5.1 题目链接

4.5.2 题目大意

给定一个正整数数组 nums和整数 k 。

要求：找出该数组内乘积小于 k 的连续的子数组的个数。

4.5.3 解题思路

滑动窗口求解。

设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口内所有数的乘积 window_product 都小于 k。使用 window_product 记录窗口中的乘积值，使用 count 记录符合要求的子数组个数。

  • 一开始，left、right 都指向 0。

  • 将最右侧元素加入当前子数组乘积 window_product 中。

  • 如果 window_product >= k ，则不断右移 left，缩小滑动窗口长度，并更新当前乘积值 window_product 直到 window_product < k。

  • 记录累积答案个数 += 1，向右移动 right，直到 right >= len(nums) 结束。

  • 输出累积答案个数。

4.5.4 代码

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        size = len(nums)
        left = 0
        right = 0
        window_product = 1
        
        count = 0
        
        while right < size:
            window_product *= nums[right]

            while window_product >= k:
                window_product /= nums[left]
                left += 1

            count += (right - left + 1)
            right += 1
            
        return count

参考资料