Проблеми з ковзним вікном — це проблеми, в яких вікно фіксованого або змінного розміру переміщується через структуру даних, як правило, масив або рядок, для ефективного вирішення задач на основі безперервних підмножин елементів. Цей прийом використовується, коли нам потрібно знайти підмасиви або підрядки відповідно до заданого набору умов.

Техніка розсувних вікон

Зміст

• Що таке техніка розсувних вікон?
• Як використовувати техніку розсувних вікон?
• Як визначити проблеми з розсувними вікнами
• Випадки використання техніки розсувних вікон
• Практичні завдання з техніки розсувних вікон

Що таке техніка розсувних вікон?

Техніка розсувних вікон це метод, який використовується для ефективного вирішення проблем, які включають визначення a вікно або діапазон у вхідних даних (масивах або рядках), а потім переміщення цього вікна по даним для виконання певної операції у вікні. Ця техніка зазвичай використовується в таких алгоритмах, як пошук підмасивів із певною сумою, пошук найдовшого підрядка з унікальними символами або розв’язання задач, які потребують вікна фіксованого розміру для ефективної обробки елементів.

Давайте візьмемо приклад, щоб зрозуміти це правильно, скажімо, у нас є масив розміру Н а також ціле число К. Тепер ми повинні точно обчислити максимальну суму підмасиву, який має розмір К. Тепер як нам підійти до цієї проблеми?

Один зі способів зробити це, взявши з масиву кожен підмасив розміром K і дізнавшись максимальну суму цих підмасивів. Це можна зробити за допомогою вкладених циклів, які призведуть до O(N²) Складність часу.

Але чи можемо ми оптимізувати цей підхід?

Відповідь: Так, замість того, щоб брати кожен К розміру підмасиву та обчислення його суми, ми можемо просто взяти один підмасив розміру K від 0 до K-1 індексу та обчислити його суму, тепер зміщувати наш діапазон одну за одною разом із ітераціями та оновлювати результат, наприклад, у наступній ітерації збільшити ліворуч і праворуч і оновіть попередню суму, як показано на зображенні нижче:

Техніка розсувних вікон

Тепер виконуйте цей метод для кожної ітерації, доки не досягнемо кінця масиву:

Техніка розсувних вікон

що таке const в java

Таким чином, ми бачимо, що замість перерахунку суми кожного підмасиву розміром K ми використовуємо попереднє вікно розміру K і використовуючи його результати, ми оновлюємо суму та зміщуємо вікно вправо, пересуваючи вказівники вліво та вправо. Ця операція є оптимальною, оскільки знадобиться час O(1), щоб зсунути діапазон замість повторного обчислення.

Цей підхід переміщення покажчиків і відповідного обчислення результатів відомий як Техніка розсувного вікна .

Як використовувати техніку розсувних вікон?

В основному розсувні вікна бувають двох типів:

1. Розсувне вікно фіксованого розміру:

Загальні кроки для вирішення цих питань, дотримуючись наведених нижче кроків.

• Знайдіть потрібний розмір вікна, скажімо К.
• Обчислити результат для 1-го вікна, тобто включити перші K елементів структури даних.
• Потім використовуйте цикл, щоб пересунути вікно на 1 і продовжувати обчислювати результат вікно за вікном.

2. Розсувне вікно змінного розміру:

Загальні кроки для вирішення цих питань, дотримуючись наведених нижче кроків.

• У цьому типі проблеми з ковзним вікном ми збільшуємо правий вказівник один за одним, доки наша умова не буде істинною.
• На будь-якому кроці, якщо наша умова не збігається, ми зменшуємо розмір нашого вікна, збільшуючи лівий покажчик.
• Знову ж таки, коли наша умова задовольняє, ми починаємо збільшувати правий покажчик і виконуємо крок 1.
• Ми виконуємо ці кроки, поки не досягнемо кінця масиву.

Як визначити проблеми з розсувними вікнами:

• Для цих завдань зазвичай потрібно знайти максимум/мінімум Підмасив , Підрядки які задовольняють певну умову.
• Розмір підмасиву або підрядка ' К’ буде подано в деяких задачах.
• Ці проблеми можна легко розв’язати в O(N²) часова складність за допомогою вкладених циклів, за допомогою ковзного вікна ми можемо їх вирішити O(n) Часова складність.
• Необхідна часова складність: O(N) або O(Nlog(N))
• Обмеження: N <= 10⁶, Якщо N є розміром масиву/рядка.

Випадки використання техніки розсувних вікон:

1. Щоб знайти максимальну суму всіх підмасивів розміру K:

Дано масив цілих чисел розміром «n», Наша мета — обчислити максимальну суму «к» послідовних елементів у масиві.

Вхідні дані: arr[] = {100, 200, 300, 400}, k = 2
Вихід: 700

Вхідні дані: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Вихід: 39
Ми отримуємо максимальну суму, додаючи підмасив {4, 2, 10, 23} розміром 4.

Вхідні дані: arr[] = {2, 3}, k = 3
Вихід: Недійсний
Немає підмасиву розміром 3, оскільки розмір усього масиву дорівнює 2.

Наївний підхід: Отже, розберемо проблему з Підхід грубої сили . Ми починаємо з першого індексу і підсумовуємо до kth елемент. Ми робимо це для всіх можливих послідовних блоків або груп з k елементів. Для цього методу потрібен вкладений цикл for, зовнішній цикл for починається з початкового елемента блоку з k елементів, а внутрішній або вкладений цикл складатиметься до k-го елемента.

Нижче наведено реалізацію вищезазначеного підходу:

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // Initialize result  int max_sum = INT_MIN;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  #include  #include  // Find maximum between two numbers. int max(int num1, int num2) {  return (num1>номер2) ? num1 : num2; } // Повертає максимальну суму в підмасиві розміром k. int maxSum(int arr[], int n, int k) { // Ініціалізація результату int max_sum = INT_MIN;  // Розглянемо всі блоки, що починаються з i.  для (int i = 0; i< n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d', maxSum(arr, n, k));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // Initialize result  int max_sum = Integer.MIN_VALUE;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed by Aditya Kumar (adityakumar129)>

# code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>

// C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG {  // Returns maximum sum in a  // subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // Initialize result  int max_sum = int.MinValue;  // Consider all blocks starting  // with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.Max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

function maxSum(arr, n, k) {  let max_sum = 0;    // Loop from i to k  for (let i = 0; i < k; i++) {  max_sum += arr[i];  }    let window_sum = max_sum;  for (let i = k; i < n; i++) {  window_sum = window_sum - arr[i - k] + arr[i];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));>

 // code ?>// O(n*k) рішення для знаходження максимальної суми // підмасиву розміру k // Повертає максимальну суму в підмасиві розміру k. function maxSum($arr, $n, $k) { // Ініціалізація результату $max_sum = PHP_INT_MIN ; // Розглянемо всі блоки // починаючи з i. для ($i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>

24>

Часова складність: O(k*n), оскільки він містить два вкладені цикли.
Допоміжний простір: О(1)

Застосування техніки розсувного вікна:

• Ми обчислюємо суму перших k елементів із n членів за допомогою лінійного циклу та зберігаємо суму в змінній window_sum .
• Потім ми будемо лінійно проходити по масиву, поки він не досягне кінця, і одночасно стежити за максимальною сумою.
• Щоб отримати поточну суму блоку з k елементів, просто відніміть перший елемент від попереднього блоку та додайте останній елемент поточного блоку.

Представлення нижче покаже, як вікно ковзає по масиву.

Розглянемо масив обр[] = {5, 2, -1, 0, 3} і значення k = 3 і п = 5

Це початкова фаза, на якій ми обчислили початкову суму вікна, починаючи з індексу 0. На цьому етапі сума вікна дорівнює 6. Тепер ми встановлюємо максимальну_суму як поточне_вікно, тобто 6.

Тепер ми пересуваємо наше вікно на індекс одиниці. Тому тепер він відкидає 5 із вікна та додає 0 до вікна. Отже, ми отримаємо нашу нову віконну суму, віднявши 5, а потім додавши до неї 0. Отже, наша віконна сума тепер стає 1. Тепер ми порівняємо цю віконну суму з максимальною_сумою. Оскільки він менший, ми не будемо змінювати максимальну суму.

приклади dfa

Подібним чином, тепер ми знову пересуваємо наше вікно на індекс одиниці й отримуємо, що нова сума вікна дорівнює 2. Знову ми перевіряємо, чи поточна сума вікна більша за максимальну_суму до цього моменту. Знову ж таки, він менший, тому ми не змінюємо максимальну_суму.
Таким чином, для наведеного вище масиву наша максимальна_сума дорівнює 6.

Нижче наведено код для вищезазначеного підходу:

// O(n) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // n must be greater  if (n <= k) {  cout << 'Invalid';  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = max(max_sum, window_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; }>

// Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // n must be greater  if (n <= k) {  System.out.println('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed // by prerna saini.>

# O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay>

// C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // n must be greater  if (n <= k) {  Console.WriteLine('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.Max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

>

 // O(n) solution for finding maximum sum of // a subarray of size k // Returns maximum sum in a  // subarray of size k. function maxSum( $arr, $n, $k) { // n must be greater if ($n <= $k) { echo 'Invalid'; return -1; } // Compute sum of first // window of size k $max_sum = 0; for($i = 0; $i < $k; $i++) $max_sum += $arr[$i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. $window_sum = $max_sum; for ($i = $k; $i < $n; $i++) { $window_sum += $arr[$i] - $arr[$i - $k]; $max_sum = max($max_sum, $window_sum); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67 ?>>

24>

Часова складність: O(n), де п це розмір вхідного масиву обр[] .
Допоміжний простір: О(1)

2. Найменший підмасив із сумою, більшою за задане значення:

Дано масив обр[] цілих чисел і числа X , завдання полягає в тому, щоб знайти найменший підмасив із сумою, більшою за задане значення.

Підхід:

Ми можемо вирішити цю проблему за допомогою техніки розсувного вікна та підтримки двох покажчиків: початку та кінця, щоб позначити початок і кінець вікна. Ми можемо продовжувати збільшувати кінцевий вказівник, доки сума вікна не буде менше або дорівнюватиме X. Коли сума вікна стає більшою за X, ми записуємо довжину вікна та починаємо переміщувати початковий вказівник до суми вікна стає меншим або дорівнює X. Тепер, коли сума стає меншою або дорівнює X, знову почніть збільшувати кінцевий покажчик. Продовжуйте рухати початковий і кінцевий вказівник, поки ми не досягнемо кінця масиву.

3. Знайти підмасив із заданою сумою в масиві цілих невід’ємних чисел:

Дано масив обр[] цілих невід’ємних чисел і цілого числа сума , знайти підмасив, який додає до заданого сума .

Підхід:

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

• Почніть з порожнього підмасиву.
• додавайте елементи до підмасиву, поки сума не стане меншою ніж x (наведена сума) .
• Якщо сума більша ніж x , видалити елементи з почати поточного підмасиву.

4. Найменше вікно, яке містить усі символи самого рядка:

Підхід:

В основному вікно символів підтримується за допомогою двох покажчиків почати і кінець . Ці почати і кінець покажчики можна використовувати для зменшення та збільшення розміру вікна відповідно. Щоразу, коли вікно містить усі символи заданого рядка, вікно зменшується з лівого боку, щоб видалити зайві символи, а потім його довжина порівнюється з найменшим знайденим вікном.
Якщо в поточному вікні більше символів не можна видалити, ми починаємо збільшувати розмір вікна за допомогою кінець доки всі окремі символи, присутні в рядку, також не з’являться у вікні. Нарешті, знайдіть мінімальний розмір кожного вікна.

Практичні завдання з техніки розсувного вікна:

Пов'язані статті:

• Р ecent Статті про техніку розсувних вікон
• Практичні запитання про розсувне вікно
• DSA Self-Paced – найбільш використовуваний і надійний курс DSA