Dois Ponteiros

Conceito

Dois ponteiros é o padrão que substitui dois laços aninhados por dois índices numa única passada — trocando O(n²) por O(n).

Existem duas famílias, e confundi-las é a fonte da maioria dos erros:

1. Pontas opostas (convergentes). lo no início, hi no fim, andando um para o outro até se cruzarem.

Isso exige ordenação (ou alguma simetria), porque o algoritmo depende de poder descartar com segurança. Se a soma s[lo]+s[hi] é grande demais, então s[hi] é grande demais para formar par com qualquer elemento restante — porque todos os restantes são ≥ s[lo]. Logo hi pode ser descartado para sempre.

É o mesmo raciocínio da 1. Busca Binária: cada passo elimina candidatos provadamente inúteis. Sem a ordenação, o descarte é injustificado e a resposta fica errada.

Casos: par com soma alvo em array ordenado, palíndromo, "maior área entre duas barras", inverter in-place.

2. Mesmo sentido (rápido/lento). Dois índices andando na mesma direção a velocidades diferentes.

Casos: remover duplicatas in-place (um índice lê, outro escreve), detectar ciclo em lista ligada (Floyd — o lento anda 1, o rápido 2, e se há ciclo eles se encontram), e 5. Sliding Window, que é o caso com estado.

Como reconhecer o padrão num enunciado que não o menciona:

• "par de elementos", "dois números que..."
• array ordenado dado de graça (é uma dica, não decoração)
• "in-place" ou "sem memória extra" — é quase sempre dois ponteiros
• "subarray contíguo" → sliding window
• "remover/mover elementos mantendo a ordem" → ponteiro de leitura e de escrita

Em Go

Não há abstração — é aritmética de índice. Mas há um idioma que vale internalizar, porque aparece em toda a stdlib: o par leitura/escrita para filtrar in-place.

escreve := 0
for le := 0; le < len(s); le++ {
	if manter(s[le]) {
		s[escreve] = s[le]
		escreve++
	}
}
s = s[:escreve] // descarta a cauda

Isso filtra sem alocar, e é exatamente o que slices.Compact, slices.Delete e slices.DeleteFunc fazem por baixo.

clear(s[escreve:]) // Go 1.21+
s = s[:escreve]

Sobre strings: s[i] numa string Go devolve um byte, não um caractere. Dois ponteiros sobre string com acentos ou emoji precisa de []rune(s) — senão você compara metades de sequências UTF-8. É a armadilha mais comum de "palíndromo" em Go.

Respostas às perguntas-guia

1. Que formato de problema esse padrão resolve?

Conceito: problemas em que a resposta envolve dois elementos ou uma região contígua, e em que você consegue provar que mover um ponteiro descarta candidatos inúteis.

Em Go: mais um formato, muito frequente na prática: filtrar ou compactar um slice in-place com ponteiro de leitura e de escrita.

2. Por que ele troca O(n²) por O(n), e o que ele exige do input (ordenado?)?

Conceito: porque cada ponteiro percorre o array no máximo uma vez — o total de movimentos é O(n), não O(n²). Pontas opostas exigem ordenação; mesmo sentido não.

Em Go: se você precisa ordenar primeiro, o custo total é O(n log n) do slices.Sort + O(n) da varredura. Frequentemente 6. Hash Map para Contagem resolve o mesmo problema em O(n) sem ordenar — a troca é memória.

3. Ponteiros nas duas pontas vs ponteiros no mesmo sentido: quando cada um?

Conceito: duas pontas quando você compara os extremos e pode descartar um deles (exige ordem). Mesmo sentido quando você transforma ou mede uma sequência (não exige ordem).

Em Go: mesmo sentido é o mais comum no dia a dia, porque é o padrão de filtro in-place.

4. Como você reconhece o padrão em um enunciado que não o menciona?

Conceept: pelas pistas: "par", "in-place", "sem memória extra", "contíguo", ou um array ordenado oferecido sem motivo aparente.

Em Go: se o enunciado diz "sem alocar", a resposta é quase certamente leitura/escrita com dois índices — porque em Go "sem alocar" é uma restrição verificável com -benchmem.

Trade-offs

Do conceito:

• O(n) em troca de exigir ordenação (nas pontas opostas). Se ordenar custa O(n log n) e você faria isso uma vez para muitas consultas, vale; se é uma consulta só, 6. Hash Map para Contagem em O(n) pode ganhar.
• In-place economiza memória e destrói o input. Se o chamador precisa do original, você trocou alocação por um bug.
• Dois ponteiros é O(1) de espaço; hash é O(n). É a troca clássica tempo/espaço vista de outro ângulo.

Em Go:

• Filtro in-place não aloca e exige lembrar de zerar a cauda quando há ponteiros.
• slices.DeleteFunc já faz certo — preferir a stdlib a reescrever o idioma.
• Sobre strings, byte vs rune é uma decisão de corretude, não de performance.

Exemplo prático

package main

import (
	"fmt"
	"slices"
	"strings"
	"unicode"
)

// --- Pontas opostas: exige ORDENADO ---
func parComSoma(s []int, alvo int) (int, int, bool) {
	lo, hi := 0, len(s)-1
	for lo < hi {
		soma := s[lo] + s[hi]
		switch {
		case soma == alvo:
			return s[lo], s[hi], true
		case soma < alvo:
			lo++ // s[lo] é pequeno demais para QUALQUER par restante
		default:
			hi-- // s[hi] é grande demais para QUALQUER par restante
		}
	}
	return 0, 0, false
}

// --- Pontas opostas sobre texto: RUNE, não byte ---
func palindromo(s string) bool {
	r := []rune(strings.ToLower(s)) // sem isto, acento quebra
	lo, hi := 0, len(r)-1
	for lo < hi {
		for lo < hi && !unicode.IsLetter(r[lo]) { lo++ }
		for lo < hi && !unicode.IsLetter(r[hi]) { hi-- }
		if r[lo] != r[hi] { return false }
		lo++
		hi--
	}
	return true
}

// --- Mesmo sentido: leitura/escrita, filtro in-place sem alocar ---
func removeDuplicatas(s []int) []int { // s ordenado
	if len(s) == 0 { return s }
	escreve := 1
	for le := 1; le < len(s); le++ {
		if s[le] != s[escreve-1] {
			s[escreve] = s[le]
			escreve++
		}
	}
	return s[:escreve]
}

func filtraPares(s []int) []int {
	escreve := 0
	for le := range s {
		if s[le]%2 == 0 {
			s[escreve] = s[le]
			escreve++
		}
	}
	clear(s[escreve:]) // libera referências na cauda (Go 1.21+)
	return s[:escreve]
}

// --- Mesmo sentido a velocidades diferentes: Floyd ---
type No struct {
	V    int
	Prox *No
}

func temCiclo(cabeca *No) bool {
	lento, rapido := cabeca, cabeca
	for rapido != nil && rapido.Prox != nil {
		lento = lento.Prox
		rapido = rapido.Prox.Prox // 2x a velocidade
		if lento == rapido {      // só se encontram se houver ciclo
			return true
		}
	}
	return false
}

func main() {
	s := []int{1, 3, 4, 6, 8, 11}
	a, b, ok := parComSoma(s, 14)
	fmt.Printf("par com soma 14: %d+%d ok=%v\n", a, b, ok)
	_, _, ok = parComSoma(s, 100)
	fmt.Println("par com soma 100:", ok)

	for _, t := range []string{"A man, a plan, a canal: Panama", "socorram-me subi no onibus em marrocos", "ana", "goiaba"} {
		fmt.Printf("%-40q palíndromo=%v\n", t, palindromo(t))
	}

	fmt.Println("sem duplicatas:", removeDuplicatas([]int{1, 1, 2, 3, 3, 3, 4}))
	fmt.Println("só pares:      ", filtraPares([]int{1, 2, 3, 4, 5, 6}))
	fmt.Println("stdlib faz igual:", slices.Compact([]int{1, 1, 2, 3, 3}))

	// lista com ciclo
	n3 := &No{V: 3}
	n2 := &No{V: 2, Prox: n3}
	n1 := &No{V: 1, Prox: n2}
	fmt.Println("sem ciclo:", temCiclo(n1))
	n3.Prox = n1 // fecha o ciclo
	fmt.Println("com ciclo:", temCiclo(n1))
}

Relacionado

• 5. Sliding Window — dois ponteiros no mesmo sentido, com estado
• 1. Busca Binária — o mesmo princípio de descarte provado
• 6. Hash Map para Contagem — a alternativa: O(n) sem ordenar, gastando memória
• 2. Array — semana 2, por que in-place é barato

Parte de Semana 04 - Algoritmos Essenciais · 00 - MOC Fundamentos de Programação