Hash Map para Contagem

Conceito

Este é o padrão de maior retorno da semana: trocar busca por contagem. Uma classe enorme de problemas O(n²) — "existe um par que...", "quantos elementos...", "qual aparece mais" — vira O(n) com uma passada e um mapa.

O insight é simples: em vez de procurar o complemento (O(n) por elemento), você lembra o que já viu (O(1) por elemento).

Os três padrões, e todos os exercícios caem num deles:

1. Frequência. Conte ocorrências e responda sobre a distribuição. → anagrama, elemento majoritário, k mais frequentes, "todos os caracteres são únicos".

2. Visto antes. Ao processar x, pergunte ao mapa se o que você precisa já passou. → two-sum em O(n): para cada x, procure alvo − x entre os já vistos. Uma passada.

3. Índice ou posição do último visto. Guarde onde viu, não só se viu. → substring sem repetição, "existe duplicata a distância ≤ k", soma de subarray igual a k (com mapa de somas de prefixo).

O terceiro é o menos conhecido e o mais poderoso: soma de prefixo + mapa resolve "quantos subarrays somam k" em O(n), um problema que parece exigir O(n²).

A troca: O(n) de memória. Ela é ruim quando:

• n é enorme e a memória é o gargalo
• você poderia ter ordenado in-place e usado 4. Dois Ponteiros com O(1) de espaço
• a entrada já vem ordenada — aí o mapa é desperdício puro

Quando um array de frequência bate o mapa: sempre que o domínio for pequeno e conhecido. 26 letras, 128 bytes ASCII, 10 dígitos, 0..1000. Um array:

• não faz hash
• não aloca (cabe na stack)
• tem localidade perfeita

A diferença é de várias vezes, não de percentual. Usar map[rune]int para contar letras minúsculas é o exemplo canônico de generalidade desnecessária.

Em Go

map[T]int com o idioma m[k]++, que funciona com chave ausente porque ler chave inexistente devolve o valor zero. Não existe if not in map em Go — o zero resolve.

[26]int para letras: é um array, fica na stack, custo zero de alocação. Em Go isso é ainda mais vantajoso que em linguagens com boxing, porque [26]int são 208 bytes contíguos.

Bytes ou runas, de novo:

for i := 0; i < len(s); i++ sobre string percorre bytes; for _, r := range s decodifica runas. Contar "letras" de "café" com o primeiro dá 5.

Para "k mais frequentes", o idioma é: conte no mapa, transfira para um slice de pares, e slices.SortFunc com cmp.Or para desempate estável. container/heap só vale quando k << n e n é grande.

Cuidado com o mapa como acumulador em concorrência: contagem paralela num mapa compartilhado é fatal error: concurrent map writes. O padrão correto é um mapa por worker e uma redução no fim — o mesmo shape de um map-reduce.

Respostas às perguntas-guia

1. Que problemas viram triviais quando você troca busca por contagem?

Conceito: todos os que perguntam "existe/quantos/qual mais" sobre pares ou multiplicidade. A busca O(n) por elemento vira consulta O(1).

Em Go: m[k]++ sem inicializar e v, ok := m[k] são os dois idiomas que cobrem praticamente todo o padrão.

2. Por que isso troca tempo por memória, e quando essa troca é ruim?

Conceito: você guarda até n chaves para não precisar reprocurar. Ruim quando a memória é o gargalo, ou quando ordenar + dois ponteiros resolveria com O(1) de espaço.

Em Go: a troca é maior do que parece — cada chave de mapa custa mais que um elemento de slice (hash, metadados, buckets). Para domínio pequeno, [N]int elimina a troca inteira.

3. Como detectar anagrama, duplicata e soma-alvo com esse padrão?

Conceito:

• anagrama — conte as duas strings e compare as contagens (ou conte a primeira e decremente com a segunda, verificando que nada fica negativo)
• duplicata — conjunto de vistos; se já está, achou
• soma-alvo — para cada x, procure alvo − x entre os vistos

Em Go: conjunto é map[T]struct{} (zero bytes por valor) ou map[T]bool (mais legível, 1 byte). Para anagrama de ASCII, [26]int e comparação direta de arrays com == — arrays são comparáveis em Go, o que deixa o código em duas linhas.

4. Quando um array de frequência simples é melhor que um hash map?

Conceito: domínio pequeno e conhecido. Sem hash, sem alocação, localidade perfeita.

Em Go: [26]int, [128]int, [256]int. E o bônus: arrays de tamanho fixo são comparáveis (a == b) e podem ser chave de mapa — nada disso vale para map[K]V nem para slice (4. Mutabilidade, semana 1).

Trade-offs

Do conceito:

• O(n) de tempo por O(n) de memória. É a troca mais rentável em problemas de entrevista e a mais perigosa em produção com dados grandes.
• Contar destrói a informação de posição, a menos que você guarde índices. Escolher entre "quantas vezes" e "onde" é a decisão de projeto.
• Array de frequência exige domínio fechado; mapa aceita qualquer chave comparável.

Em Go:

• m[k]++ com valor zero implícito elimina toda a cerimônia de inicialização.
• Mapa não é seguro para concorrência: contagem paralela precisa de redução, não de mapa compartilhado.
• Array como estado é mais rápido e permite == e uso como chave — vantagens que não existem no mapa.

Exemplo prático

package main

import (
	"cmp"
	"fmt"
	"slices"
)

// --- Padrão 2: "visto antes". Two-sum em UMA passada, O(n). ---
func doisSoma(s []int, alvo int) (int, int, bool) {
	visto := make(map[int]int, len(s)) // valor -> índice
	for i, v := range s {
		if j, ok := visto[alvo-v]; ok { // o complemento já passou?
			return j, i, true
		}
		visto[v] = i
	}
	return 0, 0, false
}

// --- Padrão 1: frequência. Array, não mapa — e arrays são comparáveis. ---
func anagrama(a, b string) bool {
	if len(a) != len(b) { return false }
	var ca, cb [26]int
	for i := 0; i < len(a); i++ {
		ca[a[i]-'a']++
		cb[b[i]-'a']++
	}
	return ca == cb // comparação de arrays: uma linha
}

// --- Padrão 3: soma de prefixo + mapa. Parece O(n²), é O(n). ---
func subarraysComSoma(s []int, k int) int {
	// contagem de somas de prefixo já vistas; prefixo 0 aparece uma vez (antes de tudo)
	cont := map[int]int{0: 1}
	soma, total := 0, 0
	for _, v := range s {
		soma += v
		total += cont[soma-k] // quantos prefixos anteriores fazem a soma dar k
		cont[soma]++
	}
	return total
}

// --- k mais frequentes: conta, transfere, ordena com desempate ---
func maisFrequentes(s string, k int) []string {
	cont := map[rune]int{}
	for _, r := range s { // range decodifica RUNAS
		cont[r]++
	}
	type par struct {
		R rune
		N int
	}
	pares := make([]par, 0, len(cont))
	for r, n := range cont {
		pares = append(pares, par{r, n})
	}
	slices.SortFunc(pares, func(a, b par) int {
		return cmp.Or(cmp.Compare(b.N, a.N), cmp.Compare(a.R, b.R)) // desc por N, asc por rune
	})
	out := []string{}
	for i := 0; i < k && i < len(pares); i++ {
		out = append(out, fmt.Sprintf("%c=%d", pares[i].R, pares[i].N))
	}
	return out
}

func main() {
	i, j, ok := doisSoma([]int{2, 7, 11, 15}, 9)
	fmt.Printf("two-sum: índices %d,%d ok=%v\n", i, j, ok)

	fmt.Println("anagrama(listen, silent):", anagrama("listen", "silent"))
	fmt.Println("anagrama(hello, world): ", anagrama("hello", "world"))

	fmt.Println("subarrays somando 2 em [1,1,1]:", subarraysComSoma([]int{1, 1, 1}, 2))
	fmt.Println("subarrays somando 3 em [1,2,3,-1,1,2]:", subarraysComSoma([]int{1, 2, 3, -1, 1, 2}, 3))

	fmt.Println("3 mais frequentes:", maisFrequentes("abracadabra", 3))

	// bytes vs runas ao contar
	s := "café"
	nb := 0
	for i := 0; i < len(s); i++ { nb++ }
	nr := 0
	for range s { nr++ }
	fmt.Printf("%q: %d bytes, %d runas\n", s, nb, nr)

	// conjunto: map[T]struct{} nao gasta byte por valor
	conjunto := map[string]struct{}{}
	for _, w := range []string{"a", "b", "a"} {
		conjunto[w] = struct{}{}
	}
	fmt.Println("elementos distintos:", len(conjunto))
}

Relacionado

• 6. Hash Map — semana 2, a estrutura que sustenta o padrão
• 4. Dois Ponteiros — a alternativa com O(1) de espaço, exigindo ordem
• 5. Sliding Window — o estado da janela é quase sempre uma contagem
• 4. Mutabilidade — semana 1, por que array serve de chave e slice não

---

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