Что такое алгоритм скользящего окна? Примеры?

Question

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

Не удалось найти учебный материал / подробности по нему.

О чем алгоритм?

Answer 1

Вообще говоря, скользящее окно - это подсписок, который работает над базовой коллекцией.То есть, если у вас есть массив типа

[a b c d e f g h]

, скользящее окно размером 3 будет работать над ним как

[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]

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

Answer 2

Скользящее окно - это метод решения проблем, включающий массивы / списки. эти проблемы легко решить при использовании метода грубой силы в O (n ^ 2) или O (n ^ 3), но для их решения в O (n) требуется более сложный подход.

Отличная статья на эту тему здесь: https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66

Answer 3

Это код протокола скользящего окна для массива размера n, где сумма чисел k хранится вместе в другой сумме массива. Следующий код в Java.

import java.io.*;
class deva
{
    public static void main(String args[])throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[] a = new int[n];
        for(int i=0; i<n; i++)
            a[i] = Integer.parseInt(in.readLine());
        int k = Integer.parseInt(in.readLine());
        int[] sum = new int[n-k+1];
        for(int i=0; i<k; i++)
            sum[0] += a[i];
        System.out.println(sum[0]);
        for(int i=1; i<n-k+1; i++)
        {
            sum[i] = sum[i-1] + a[i+k-1] - a[i-1];
            System.out.println(sum[i]);
        }
    }
}