Cracking the Coding Interview: Part The Sliding Window Pattern

在我们系列的第二部分中，我们深入研究解决编码面试问题的最通用的模式之一：滑动窗口。此技术对于优化涉及连续元素的子数组或子字符串的问题非常有用，例如最大化总和、查找序列中的特定条件或处理字符串中的子字符串。

在我们开始之前，如果您正在寻找准备编码面试的全面指南，请考虑查看《破解编码面试》，这是任何认真想在顶级科技公司找到工作的人的必备书籍。

滑动窗口模式概述

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

何时使用滑动窗口：

• 问题涉及连续的子数组或子字符串。
• 您需要找到数据集滑动范围内的最大或最小总和、计数或其他条件。
• 它涉及固定的窗口大小或需要扩展或缩小的动态窗口。

---

滑动窗口方法的类型

1. 固定大小滑动窗口

• 它是什么：一个固定大小的窗口，可以在数组或字符串上滑动，同时保持总和或乘积等运行条件。
• 示例：求大小为 k 的子数组的最大和。

示例问题：给定一个整数数组和一个数字 k，找到大小为 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

说明：

• 大小为 k 的窗口被初始化。
• 当窗口在数组上移动时，通过减去不再在窗口中的元素并添加进入窗口的新元素来实现滑动效果。
• 这将问题从 O(n*k) 的强力方法优化为 O(n)，因为我们不再需要为每次迭代求和整个窗口。

---

2. 动态滑动窗口

• 它是什么：当窗口大小不固定时使用。窗口根据问题的要求（例如满足总和或条件）扩展或收缩。
• 示例：查找总和大于或等于 S 的最小子数组。

示例问题：给定一个整数数组和一个数字 S，找到总和大于或等于 S 的最小连续子数组。

  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

说明：

• 窗口通过增加window_end来扩展，直到总和超过或等于S。
• 一旦满足条件，窗口开始从左侧收缩（window_start）以找到最小子数组大小。
• 这种方法非常高效，因为它通过避免重新计算将问题从 O(n^2) 减少到 O(n)。

---

实施滑动窗口解决方案的步骤

1. 定义窗口边界：您需要定义窗口的开始和结束。

2. 设置初始条件：对于固定窗口，初始化第一个窗口的和/乘积/条件。对于动态窗口，初始条件取决于问题的目标。

3. 滑动窗口：

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

4. 检查并更新结果：每次窗口移动后，根据需要更新结果（例如最大总和、最小长度等）。

---

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

1. 最长无重复字符的子串

   • 问题：给定一个字符串s，求最长不包含重复字符的子串的长度。
   • 模式：使用动态滑动窗口扩大直到找到重复字符，然后缩小窗口直到满足条件。

2. 大小为 K 的最大和子数组

   • Problem: Given an array of integers and an integer k, find the maximum sum of any subarray of size k.
   • Pattern: Use a fixed size sliding window to maintain the sum of k elements and update the maximum sum as you slide the window across the array.

3. Smallest Subarray with a Given Sum

   • Problem: Given an array of positive integers and a number S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S.
   • Pattern: Use a dynamic sliding window that expands to find a valid subarray and contracts to minimize its length.

---

Sliding Window Hacks for Interviews

1. Think in terms of the window boundaries: Start by thinking about where the window should start and end. This helps you identify the exact range you're working with.

2. Use a hashmap or set for dynamic windows: When dealing with substrings or unique elements, use a set to track the elements in the window.

3. Start with brute-force and then optimize: In some problems, starting with a brute-force approach (like checking every possible subarray) can help you visualize how a sliding window would reduce unnecessary work.

4. Look for optimal conditions: If the problem has an optimization component (like minimizing or maximizing a sum or length), sliding window may be a good fit.

---

Conclusion

The Sliding Window pattern is a powerful tool for solving many coding interview problems, especially those involving sequences like arrays or strings. By mastering both fixed-size and dynamic sliding windows, you can tackle a wide range of problems more efficiently.

In the next article, we’ll explore the Two Pointer Technique, another highly effective strategy that often complements the sliding window approach in problems that involve pairs or comparisons between elements.

Stay tuned for Part 3!

The above is the detailed content of Cracking the Coding Interview: Part The Sliding Window Pattern. For more information, please follow other related articles on the PHP Chinese website!