破解編碼面試：滑動視窗模式的一部分-js教程-PHP中文網

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)。

實施滑動視窗解決方案的步驟

定義視窗邊界：您需要定義視窗的開始和結束。
設定初始條件：對於固定窗口，初始化第一個窗口的和/乘積/條件。對於動態窗口，初始條件取決於問題的目標。
滑動視窗：
- 對於固定視窗大小：透過新增下一個元素並刪除不再位於視窗中的元素來移動視窗。
- 對於動態視窗：根據您想要滿足的條件擴展或收縮視窗。
檢查並更新結果：每次視窗移動後，根據需要更新結果（例如最大總和、最小長度等）。

使用滑動視窗的常見面試問題

最長無重複字元的子字串
- 問題：給定一個字串s，求最長不包含重複字元的子字串的長度。
- 模式：使用動態滑動視窗擴大直到找到重複字符，然後縮小視窗直到滿足條件。
大小為 K 的最大和子數組
- 問題: 整数の配列と整数 k が与えられた場合、サイズ k の部分配列の最大合計を求めます。
- パターン: 固定サイズのスライディングウィンドウを使用して、k 要素の合計を維持し、配列全体でウィンドウをスライドさせると最大合計を更新します。
指定された合計を持つ最小の部分配列
- 問題: 正の整数の配列と数値 S を指定して、合計が S 以上である最小の連続部分配列の長さを見つけます。
- パターン: 有効な部分配列を見つけるために拡張し、その長さを最小化するために縮小する動的スライディングウィンドウを使用します。

面接のためのスライディングウィンドウハック

ウィンドウの境界の観点から考える: ウィンドウの開始位置と終了位置を考えることから始めます。これは、作業している正確な範囲を識別するのに役立ちます。
動的ウィンドウにはハッシュマップまたはセットを使用します: 部分文字列または一意の要素を扱う場合は、セットを使用してウィンドウ内の要素を追跡します。
総当たりで開始してから最適化する: 問題によっては、総当たりのアプローチ (考えられるすべてのサブ配列をチェックするなど) から始めると、スライディングウィンドウがどのように不必要なデータを削減するかを視覚化するのに役立ちます。仕事。
最適な条件を探す: 問題に最適化コンポーネント (合計や長さの最小化または最大化など) がある場合は、スライディングウィンドウが適している可能性があります。