在我们系列的第二部分中，我们进入了解决编码访谈问题的最广泛的模式之一：滑动窗口。该技术对于优化涉及连续元素的子阵列或子字的问题非常有用，例如最大化总和，在序列中找到特定条件或使用字符串中的子字符串。

滑动窗口模式的概述

滑动窗口模式是一种使您可以有效地解决需要从较大数据集中考虑数据子集的问题（例如数组的子阵列或字符串的子字符串）。该技术并没有在每次移动窗口时都要重新计算子集，而是要保持运行的总或条件，从而在数据上滑动以最大程度地减少不必要的工作。

问题涉及连续的子阵列或子字符串。

您需要在数据集的滑动范围内找到最大或最小总和，计数或其他条件。

滑动窗口的类型
1。
• 修复了大小滑动窗口

：固定尺寸的窗口，该窗口在维护诸如SUM或产品之类的运行条件时滑过数组或字符串。

• 示例问题：给定一个整数和一个数字k，找到大小为k的任何子阵列的最大总和。
def max_sum_subarray（arr，k）： ＃初始化变量以存储最大总和和当前窗口总和。 max_sum = 0 window_sum = 0 ＃首先，计算初始窗口的总和（第一个“ k”元素）。 对于我的范围（k）： window_sum = arr [i] ＃将max_sum设置为初始窗口的总和。 max_sum = window_sum ＃现在，将窗口滑过数组。 ＃从KTH元素开始，然后移动到数组的末尾。 对于我的范围（K，Len（arr））： ＃通过减去不再在窗口中的元素来滑动窗口 ＃（arr [i -k]）并添加新元素（arr [i]）。 window_sum = arr [i] -arr [i -k] ＃更新max_sum如果当前窗口总和大于以前的max_sum。 max_sum = max（max_sum，window_sum） ＃返回找到的最大总和。 返回max_sum
• 解释
：

初始化了大小k的窗口。
窗口在整个数组中移动时，通过减去不再在窗口中的元素并添加进入窗口的新元素来实现滑动效果。

def max_sum_subarray(arr, k):
    # Initialize variables to store the maximum sum and the current window sum.
    max_sum = 0
    window_sum = 0

    # First, calculate the sum of the initial window (first 'k' elements).
    for i in range(k):
        window_sum  = arr[i]

    # Set the max_sum to the initial window's sum.
    max_sum = window_sum

    # Now, slide the window across the array. 
    # Start from the kth element and move until the end of the array.
    for i in range(k, len(arr)):
        # Slide the window by subtracting the element that is no longer in the window 
        # (arr[i - k]) and adding the new element (arr[i]).
        window_sum  = arr[i] - arr[i - k]

        # Update max_sum if the current window sum is greater than the previous max_sum.
        max_sum = max(max_sum, window_sum)

    # Return the maximum sum found.
    return max_sum

2。

是什么
• ：当窗口大小未固定时使用。窗口根据问题的要求扩展或合同（例如满足总和或条件）。

：给定一个整数和一个数字s，找到最小的连续子阵列，其总和大于或等于s。 def smallest_subarray_with_sum（arr，s）： ＃初始化变量： ＃window_sum：存储当前窗口的总和。 ＃min_length：存储找到最小子阵列的长度。 ＃window_start：滑动窗口的起始索引。 window_sum = 0 min_length = float（'inf'）＃从大量开始，以比较最小长度。 window_start = 0 ＃在数组上迭代window_end是窗口的正确边界。 对于window_end（len（arr））中的window_end： ＃将当前元素添加到window_sum。 window_sum = arr [window_end] ＃虽然当前窗口的总和大于或等于s： whindow_sum> = s： ＃如果较小，则计算当前窗口大小并更新min_length。 min_length = min（min_length，window_end -window_start 1） ＃通过在window_start处删除元素，从左侧收缩窗口。 window_sum- = arr [window_start] ＃将窗口的开始向右移动。 window_start = 1 ＃如果更新了min_length，请返回；否则，返回0（意味着找不到有效的子阵列）。 返回min_length如果min_length！= float（'inf'）else 0

• 解释：
• 窗口通过增加window_end扩展，直到总和超过或等于s。 一旦满足条件，窗口就会从左侧（window_start）开始收缩以找到最小的子阵列大小。 这种方法是有效的，因为它通过避免重新计算将问题从O（n^2）减少到O（n^2）。

实现滑动窗口解决方案的步骤
定义窗口边界

  def smallest_subarray_with_sum(arr, S):
    # Initialize variables:
    # window_sum: to store the sum of the current window.
    # min_length: to store the length of the smallest subarray found.
    # window_start: the starting index of the sliding window.
    window_sum = 0
    min_length = float('inf')  # Start with a large number to compare minimum lengths.
    window_start = 0

    # Iterate over the array with window_end being the right boundary of the window.
    for window_end in range(len(arr)):
        # Add the current element to the window_sum.
        window_sum  = arr[window_end]

        # While the current window's sum is greater than or equal to S:
        while window_sum >= S:
            # Calculate the current window size and update min_length if smaller.
            min_length = min(min_length, window_end - window_start   1)

            # Shrink the window from the left by removing the element at window_start.
            window_sum -= arr[window_start]

            # Move the start of the window to the right.
            window_start  = 1

    # If min_length was updated, return it; otherwise, return 0 (meaning no valid subarray was found).
    return min_length if min_length != float('inf') else 0

：对于固定的Windows，初始化第一个窗口的sum/product/product/条件。对于动态窗口，初始条件取决于问题的目标。 滑动窗口

用于固定窗口大小：通过添加下一个元素并删除窗口中不再的元素来移动窗口。
用于动态窗口：根据您要满足的条件展开或收缩窗口。

使用滑动窗口的常见面试问题

1. [2

问题
2. ：给定一个字符串，找到最长的子字符串的长度而无需重复字符。

   模式：使用动态滑动窗口展开直到找到重复的字符，然后收缩窗口直到满足条件为止。

3. [2

   ：使用固定的大小滑动窗口来维护k元素的总和，并在将窗口滑过数组时更新最大总和。
   • [2
4. 模式

   ：使用一个动态滑动窗口，该窗口扩展以找到有效的子阵列并合同以最小化其长度。

：开始思考窗口应在哪里开始和结束。这可以帮助您确定正在使用的确切范围。

1. 使用hashmap或用于动态窗口的设置：在处理substrings或unique元素时，请使用集合来跟踪窗口中的元素。

   从蛮力开始，然后优化
   ：在某些问题中，从蛮力方法开始（例如检查每个可能的子阵列）可以帮助您可视化滑动窗口如何减少不必要的工作。
   • 寻找最佳条件：如果问题具有优化组件（例如最小化或最大化总和或长度），则滑动窗口可能很合适。
   • 结论 滑动窗口模式是解决许多编码访谈问题的强大工具，尤其是涉及数组或字符串序列的编码面试问题。通过掌握固定尺寸和动态滑动窗口，您可以更有效地解决广泛的问题。
   在下一篇文章中，我们将探索
，这是另一种高效的策略，通常在涉及元素对成对或比较的问题中的滑动窗口方法中进行补充。

2. 请关注第3部分！