В этой второй части нашей серии мы погружаемся в один из самых универсальных шаблонов для решения вопросов кодирования: раздвижное окно. Этот метод невероятно полезен для оптимизации проблем, связанных с подборами или подстроками смежных элементов, таких как максимизация сумм, поиск конкретных условий в последовательности или работа с подстроками в строках.

, прежде чем мы начнем, если вы ищете всеобъемлющее руководство по подготовке к собеседованиям по кодированию, рассмотрите возможность проверки взлома интервью по кодированию, обязательную книгу для всех, кто серьезно относится к работе в ведущих технологических компаниях.

] Обзор рисунка скользящего окна

]

шаблон скользящего окна - это метод, который позволяет эффективно решать проблемы, в которых вам необходимо рассмотреть подмножество данных из более крупного набора данных (как субрай массива или подстроение строки). Вместо того, чтобы пересматривать подмножество каждый раз, когда вы перемещаете окно, этот метод поддерживает общее количество или условия, скользя по данным, чтобы минимизировать ненужную работу.

]

] Когда использовать скользящее окно:

]

]
• проблема включает в себя смежные субрайры или подстроки.
]
• вам нужно найти максимальную или минимальную сумму, количество или другие условия в диапазоне скольжения набора данных.
]
• он включает в себя фиксированный размер окна или требует динамического окна, которое расширяется или сокращается.
]

]

---

]

] Типы подходов скользящего окна

]

] 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 до тех пор, пока сумма не превысит или равна с.
• , как только условие будет выполнено, окно начинает сжиматься слева (window_start), чтобы найти минимальный размер субрай.
]
• Этот подход эффективен, потому что он уменьшает проблему от O (n^2) до O (n), избегая рекомпутации.
]

]

---

]

] Шаги по реализации решений скользящих окон

]

]

1. определить границы окна : вам нужно определить начало и конец окна.

]

2. установите начальное условие : для фиксированных Windows, инициализируйте условие/продукт/продукт/условие для первого окна. Для динамических окон, начальное условие зависит от цели проблемы.

]
3. ]

   скользит окно :

   ]
   ]
   • для фиксированного размера окна: переключить окно, добавив следующий элемент и удалив элемент, которого больше нет в окне.
   ]
   • для динамических Windows: развернуть или сжать окно на основе состояния, которое вы пытаетесь удовлетворить.
   ]
]

4. проверить и обновлять результаты : после каждого движения окна, обновите результат (например, максимальная сумма, минимальная длина и т. Д.) При необходимости.

]

]

---

]

] Общие вопросы интервью с использованием скользящего окна

]

]
1. ]

   самая длинная подстроение без повторяющихся символов

   ]
   ]
   • ] Проблема : указано в строке S, найдите длину самой длинной подстроения без повторяющихся символов.
   ]
   • ] pattern : Используйте динамическое скользящее окно, чтобы развернуть, пока не найден дублированный символ, затем сжимайте окно, пока условие не будет удовлетворено.
   ]
   ]
]
2. ]

   максимальная сумма subarray of size k

   ]
   ]
   • ] Проблема ]: Учитывая массив целых чисел и целое число k, найдите максимальную сумму любого субрайного размера k.
   • ] pattern : используйте скользящее окно с фиксированным размером, чтобы поддерживать сумму k элементов и обновить максимальную сумму, когда вы продвигаете окно через массив.
   ]
   ]
]
3. ]

   маленький Subarray с данной суммой

   ]
   ]
   • ] Проблема ]: Учитывая массив положительных целых чисел и числа S, найдите длину наименьшего смежного субрайя, сумма которого больше или равна s.
   ]
   • ] pattern : используйте динамическое скользящее окно, которое расширяется, чтобы найти действительный субрай и контракты, чтобы минимизировать его длину.
   ]
   ]
]

]

---

]

] Раздвижные взломы окна для интервью

]

]

1. подумайте в терминах границ окна : начните с размышления о том, с чего следует начинать и закончить. Это помогает вам определить точный диапазон, с которым вы работаете.

]

2. Используйте HASHMAP или SET для Dynamic Windows : при работе с подстроками или уникальными элементами, используйте набор, чтобы отслеживать элементы в окне.

3. начните с грубого сила, а затем оптимизировать

   : в некоторых проблемах, начиная с подхода грубой силы (например, проверка каждого возможного Subarray) может помочь вам визуализировать, как раздвижное окно уменьшит ненужную работу.

   ищите оптимальные условия
: если проблема имеет компонент оптимизации (например, минимизация или максимизация суммы или длины), скользящее окно может быть хорошим.

4. ] ] ]

   ] Заключение
]

шаблон скользящего окна является мощным инструментом для решения многих задач интервью кодирования, особенно тех, которые включают такие последовательности, как массивы или строки. Освоив как фиксированные, так и динамические скользящие окна, вы можете решить широкий спектр проблем более эффективно.

---

]

в следующей статье мы рассмотрим

Two Pointer Technique

, еще одна высокоэффективная стратегия, которая часто дополняет подход скользящего окна в задачах, которые включают пары или сравнения между элементами.

]

следите за частью 3! ] ]

]