Padrões de dois ponteiros e janelas deslizantes

Padrão 1: Janela constante (como janela = 4 ou algum valor inteiro)

Por exemplo, dada uma matriz de números inteiros (-ve e ve), encontre a soma máxima para a janela contígua de tamanho k.

Padrão 2:(Tamanho variável da janela) Maior subarray/substring com exemplo: soma

• Abordagens:
  • Força Bruta: Gere todos os subarranjos possíveis e escolha o subarranjo de comprimento máximo com soma
• Melhor/Ótimo: Faça uso de dois ponteiros e janela deslizante para reduzir a complexidade do tempo para O(n)

Padrão 3: Número de subarray/substring onde como sum=k.
Isso é muito difícil de resolver porque fica difícil quando expandir (right ) ou quando encolher (left ).

Este problema pode ser resolvido usando o Padrão 2
Para resolver problemas como encontrar o número de substrings onde sum =k.

• Isso pode ser dividido em

  • Encontre submatrizes onde soma
  • Encontre submatriz onde soma

Padrão 4: Encontre a janela mais curta/mínima

Abordagens diferentes para o padrão 2:
Exemplo: Maior submatriz com soma

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? 
            }
        }

Melhor abordagem usando os dois ponteiros e a janela deslizante

        //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 



Abordagem ideal: 

Sabemos que se encontrarmos o subarray, armazenamos seu comprimento em maxLen, mas ao adicionar arr[right] se a soma se tornar maior que k, então atualmente estamos diminuindo para a esquerda fazendo sum = sum-arr[left] e fazendo left . 

Sabemos que o comprimento máximo atual é maxLen, se continuarmos diminuindo o índice esquerdo, poderemos obter outro subarray que satisfaça a condição ( maxLen, então apenas maxLen será atualizado.

Uma abordagem ideal será reduzir apenas a esquerda, desde que o comprimento do subarray seja maior que maxLen quando o subarray não estiver satisfazendo a condição (


        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