Método da janela deslizante

3.1 Definição do método da janela deslizante.

Método da Janela Deslizante (Sliding Window) — É uma técnica utilizada para resolver problemas em arrays ou strings, na qual um subarray (ou substring) fixo é movido pelos dados com o objetivo de encontrar a solução ótima. Isso permite processar elementos em uma janela de tamanho fixo e dinamicamente alterar a janela dependendo das condições do problema.

Essa técnica é especialmente útil para problemas relacionados a sequências de dados, como arrays ou strings, e ajuda a reduzir a complexidade temporal em comparação com abordagens mais ingênuas.

Princípios básicos

• Inicialização da janela: Defina o início e o fim da janela nas posições iniciais.
• Deslocamento da janela: Mova sequencialmente as bordas da janela, adicionando elementos de um lado e removendo elementos do outro.
• Processamento da janela: Em cada passo, execute os cálculos necessários para a janela atual.

Complexidade temporal e espacial do método da janela deslizante

Complexidade temporal:

• O(n) — na maioria dos casos, já que o ponteiro ou a janela se move linearmente pelo array, verificando cada posição possível da janela.

Complexidade espacial:

• O(1) — se é usado um número fixo de memória adicional para armazenar os valores atuais.
• O(k) — se for necessário armazenar elementos dentro da janela atual de tamanho k.

3.2 Encontrando a soma máxima do subarray.

Encontrando a soma máxima de um subarray de tamanho fixo

Problema:

Encontrar o subarray de tamanho fixo k com a soma máxima.

Solução:

Usamos o método da janela deslizante para manter a soma atual do subarray e atualizar a soma máxima à medida que a janela se move.

Complexidade temporal: O(n).

Exemplo de código em Python:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 Encontrando todas as anagramas da substring na string

Problema:

Encontrar todas as anagramas de uma substring dada p na string s.

Solução:

Usamos o método da janela deslizante para manter um dicionário de frequência dos caracteres da janela atual e comparar com o dicionário de frequência da substring.

Complexidade temporal: O(n).

Exemplo de código em Python:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 Encontrando o subarray mínimo

Encontrando o subarray mínimo com soma maior que o valor dado

Problema:

Encontrar o subarray mínimo cuja soma dos elementos é maior que o valor dado S.

Solução:

Usamos o método da janela deslizante para expandir a fronteira direita até que a soma seja maior que S, depois movemos a fronteira esquerda para minimizar o comprimento do subarray.

Complexidade temporal: O(n).

Exemplo de código em Python:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len