シリーズのこの第2部では、コーディングインタビューの質問を解決するための最も用途の広いパターンの1つであるスライドウィンドウに飛び込みます。この手法は、合計の最大化、シーケンス内の特定の条件を見つける、文字列内のサブストリングの操作など、隣接する要素のサブアレイまたはサブストリングを含む問題を最適化するのに非常に役立ちます。

。

始める前に、コーディングインタビューの準備のための包括的なガイドを探している場合は、コーディングインタビューのクラッキングをチェックすることを検討してください。

スライドウィンドウパターンの概要

スライディングウィンドウパターンは、より大きなデータセットからのデータのサブセットを検討する必要がある問題を効率的に解決できる手法です（配列のサブアレイや文字列のサブストリングなど）。ウィンドウを移動するたびにサブセットを再計算する代わりに、この手法は実行されている合計または条件を維持し、不必要な作業を最小限に抑えるためにデータをスライドさせます。

。

スライドウィンドウを使用する時期：

問題には、隣接するサブアレイまたはサブストリングが含まれます。
データセットのスライド範囲内の最大または最小合計、カウント、またはその他の条件を見つける必要があります。
固定されたウィンドウサイズを伴うか、展開または縮小する動的ウィンドウが必要です。

---

スライドウィンドウの種類アプローチ

1。

それが何なのか

：合計や製品などの実行条件を維持しながら配列または文字列を横切ってスライドする固定サイズのウィンドウ。
• 。 例
：サイズkのサブアレイの最大合計を見つけます
例問題

：整数と数のkの配列が与えられた場合、サイズkのサブアレイの最大合計を見つけます

def max_sum_subarray（arr、k）： ＃変数を初期化して、最大合計と現在のウィンドウ合計を保存します。 max_sum = 0 window_sum = 0 ＃最初に、初期ウィンドウの合計（最初の 'k'要素）を計算します。 範囲（k）のIのために： window_sum = arr [i] ＃max_sumを最初のウィンドウの合計に設定します。 max_sum = window_sum ＃次に、アレイ全体にウィンドウをスライドさせます。 ＃kth要素から起動し、配列の最後まで移動します。 範囲のi（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を返します

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以上の最小の隣接サブアレイを見つけます。

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 in Range（len（arr））の場合： ＃現在の要素をwindow_sumに追加します。 window_sum = arr [window_end] ＃現在のウィンドウの合計はs以上ですが、 while whind_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！= float（ 'inf'）else 0を返します
説明

：

  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

合計がs。 条件が満たされると、ウィンドウは左（window_start）から収縮し始めて、最小サブアレイサイズを見つけます。。

このアプローチは、再構成を回避することにより、O（n^2）からO（n）に問題を減らすため、効率的です。

スライドウィンドウソリューションを実装する手順

ウィンドウの境界を定義します

---

：ウィンドウの開始と終了を定義する必要があります。

1. 初期条件：固定ウィンドウの場合、最初のウィンドウの合計/製品/条件を初期化します。動的なウィンドウの場合、初期条件は問題の目標に依存します。

2. ウィンドウをスライドします：

固定されたウィンドウサイズの場合：次の要素を追加し、ウィンドウにない要素を削除してウィンドウをシフトします。

3. 動的ウィンドウの場合：満足しようとしている状態に基づいてウィンドウを展開または縮小します。

   結果を確認して更新します
   • ：各ウィンドウの動きの後、必要に応じて結果（最大合計、最小長など）を更新します。

4. スライドウィンドウを使用した一般的なインタビューの質問

文字を繰り返すことなく長いサブストリング

---

1. 問題

   ：文字列sが与えられた場合、文字を繰り返すことなく最長のサブストリングの長さを見つけます。

   パターン
   ：ダイナミックスライディングウィンドウを使用して、重複した文字が見つかるまで展開し、条件が満たされるまでウィンドウを収縮させます。
   • サイズの最大subアレイk
2. 問題

   ：整数と整数kの配列が与えられた場合、サイズkのサブアレイの最大合計を見つけます。。

   パターン
   ：固定サイズのスライディングウィンドウを使用して、k要素の合計を維持し、配列を横切ってウィンドウをスライドするときに最大合計を更新します。
   • 与えられた合計で最小のサブアレイ
問題
3. ：正の整数と数のsの配列が与えられた場合、合計がs以上の最小の隣接するサブアレイの長さを見つけます。

   パターン

   ：拡張する動的なスライディングウィンドウを使用して、有効なサブアレイと契約を見つけてその長さを最小限に抑えます。
   • インタビューのためのスライドウィンドウハック
ウィンドウの境界について考える

：ウィンドウがどこで開始して終わるべきかを考えることから始めます。これにより、使用している正確な範囲を特定するのに役立ちます。

---

1. を使用するか、ダイナミックウィンドウに設定

   ：サブストリングまたはユニークな要素を扱うときは、セットを使用してウィンドウ内の要素を追跡します。

2. はブルートフォースから始めてから

   を最適化します：いくつかの問題では、ブルートフォースアプローチ（すべての可能なサブアレイをチェックするなど）から始めて、スライドウィンドウが不要な作業を減らす方法を視覚化するのに役立ちます。

   最適な条件を探します
：問題に最適化コンポーネントがある場合（合計や長さの最小化または最大化など）、スライドウィンドウは適切な場合があります。

3. 結論
4. スライディングウィンドウパターンは、多くのコーディングインタビューの問題、特に配列や文字列などのシーケンスを含む強力なツールです。固定サイズと動的なスライドウィンドウの両方を習得することにより、幅広い問題により効率的に取り組むことができます。

   次の記事では、 2つのポインター手法

   を調べます。
パート3によるとチューシングしてください！

---