Método dos Dois Ponteiros

2.1 Definição do Método dos Dois Ponteiros

Método dos Dois Ponteiros — é uma técnica usada para resolver várias tarefas com arrays e strings, onde se usam dois ponteiros (índices) que se movem pelos dados seguindo certas regras. Esse método permite resolver eficientemente problemas relacionados à busca de pares de elementos ou subconjuntos que satisfaçam condições específicas.

Este método envolve o uso de dois ponteiros que geralmente são inicializados nos extremos opostos da estrutura de dados e se movem um em direção ao outro ou de acordo com uma regra específica. O Método dos Dois Ponteiros pode reduzir significativamente a complexidade de tempo do algoritmo em comparação com abordagens mais ingênuas.

Princípios básicos

1. Inicialização dos dois ponteiros: Os ponteiros podem ser posicionados no início e no fim do array ou string, ou em índices diferentes, dependendo da tarefa.
2. Movimento dos ponteiros: Os ponteiros se movem de acordo com uma regra específica (por exemplo, ambos os ponteiros movem-se em direção ao centro, ou um ponteiro avança enquanto o outro permanece parado).
3. Verificação da condição: A cada passo, uma condição é verificada, determinando o próximo movimento dos ponteiros ou o término do algoritmo.

Complexidade de tempo:

O(n) — na maioria dos casos, já que ambos os ponteiros percorrem o array uma ou mais vezes, mas não mais do que O(n) iterações no total.

Para algumas tarefas, dependendo das condições e das posições iniciais dos ponteiros, a complexidade de tempo pode ser O(n log n) ou O(n^2), mas isso é raro.

Exemplos de problemas resolvidos pelo método dos dois ponteiros:

2.2 Busca de dois números em um array cuja soma é igual a um número dado

Problema:

Encontre dois números em um array ordenado cuja soma seja igual ao número dado target.

Solução:

Inicialize um ponteiro no início do array e outro no final. Verifique a soma dos elementos nos ponteiros:

• Se a soma for igual a target, retorne os índices.
• Se a soma for menor que target, mova o ponteiro esquerdo para a direita.
• Se a soma for maior que target, mova o ponteiro direito para a esquerda.

Complexidade de tempo: O(n).

Exemplo de código em Python:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 Verificação de palíndromo

Problema:

Verifique se uma string é um palíndromo.

Solução:

Inicialize ponteiros no início e no fim da string. Compare os caracteres nos ponteiros:

• Se os caracteres forem iguais, mova ambos os ponteiros um em direção ao outro.
• Se os caracteres não forem iguais, a string não é um palíndromo.

Complexidade de tempo: O(n).

Exemplo de código em Python:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 Remoção de duplicatas de um array ordenado

Problema:

Remova duplicatas de um array ordenado.

Solução:

Use dois ponteiros, um para a posição atual no array resultante e outro para percorrer todos os elementos:

• Se o elemento atual não for igual ao anterior, escreva-o no array resultante.

Complexidade de tempo: O(n).

Exemplo de código em Python:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index