Шаблоны двух указателей и скользящих окон

Шаблон 1: Постоянное окно (например, окно = 4 или какое-либо целое число)

Например, учитывая массив целых чисел (-ve и ve), найдите максимальную сумму для непрерывного окна размера k.

Шаблон 2:(Переменный размер окна) Самый большой подмассив/подстрока с . Пример: sum

• Подходы:
  • Грубая сила: Сгенерируйте все возможные подмассивы и выберите подмассив максимальной длины. с суммой
• Беттен/Оптимально: Используйте два указателя и скользящее окно, чтобы уменьшить временную сложность до O (n).

Шаблон 3: номер подмассива/подстроки, где , например sum=k.
Эту проблему очень сложно решить, потому что становится трудно определить, когда расширять (справа) или когда сжимать (слева).

Эту проблему можно решить, используя Шаблон 2
Для решения таких задач, как поиск количества подстрок, в которых sum =k.

• Это можно разделить на

  • Найти подмассивы, где sum
  • Найти подмассив, в котором sum

Шаблон 4: Найдите самое короткое/минимальное окно

Различные подходы для шаблона 2:
Пример: Самый большой подмассив с суммой

public class Sample{
    public static void main(String args[]){
        n = 10;
        int arr[] = new int[n];

        //Brute force approach for finding the longest subarray with sum  k) break; /// optimization if the sum is greater than the k, what is the point in going forward? 
            }
        }

Лучше использовать два указателя и скользящее окно

        //O(n n) in the worst case r will move from 0 to n and in the worst case left will move from 0 0 n as well so 2n
        int left = 0;
        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){
                sum = sum-arr[left];
                left  ;
            }
            if(sum 



Оптимальный подход: 

Мы знаем, что если мы находим подмассив, мы сохраняем его длину в maxLen, но при добавлении arr[right] если сумма становится больше k, то в настоящее время мы сжимаемся влево, выполняя sum = sum-arr[left] и выполняя left . 

Мы знаем, что текущая максимальная длина равна maxLen. Если мы продолжим сжимать левый индекс, мы можем получить еще один подмассив, удовлетворяющий условию ( maxLen, тогда будет обновлен только maxLen.

Оптимальным подходом будет сжимать левую часть только до тех пор, пока длина подмассива превышает maxLen, когда подмассив не удовлетворяет условию (


        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){// this will ensure that the left is incremented one by one (not till the sum