Semanas 2 y 3 Arrays Strings Hashing y Sumas de Prefijos

Semanas 2 y 3: Arrays, Strings, Hashing y Sumas de Prefijos

Objetivo

Dominar problemas comunes de conteo, frecuencia, índices, normalización de strings y sumas acumuladas usando estructuras estándar de Rust.

Problemas Completados

Problema	Patrón	Función	Tests
Two Sum	Búsqueda de complemento	two_sum	3
Valid Anagram	Conteo de frecuencias	valid_anagram	3
Contains Duplicate	Pertenencia en set	contains_duplicate	2
Isomorphic Strings	Mapeo bidireccional	is_isomorphic	2
Word Pattern	Bijección patrón-palabra	word_pattern	2
Group Anagrams	Llave canónica	group_anagrams	2
Product of Array Except Self	Prefijo/sufijo	product_except_self	3
Top K Frequent Elements	Ranking por frecuencia	top_k_frequent	2
First Unique Character	Conteo + orden original	first_unique_char	2
Longest Consecutive Sequence	Inicios de secuencia en set	longest_consecutive	3
Subarray Sum Equals K	Suma de prefijos + HashMap	subarray_sum_equals_k	4

Ideas Clave

HashMap para Complementos

El mapa guarda valores anteriores. Si target - value ya existe, encontramos una pareja válida sin hacer una búsqueda cuadrática.

Conteo de Frecuencias

Se usa cuando la respuesta depende de cuántas veces aparece un valor o carácter.

Ejemplos:

• valid_anagram
• top_k_frequent
• group_anagrams
• first_unique_char

Mapeo Bidireccional

Se usa cuando dos dominios deben mantener una relación uno a uno.

Ejemplos:

• is_isomorphic
• word_pattern

Invariante:

• Si un carácter ya tiene destino, debe volver a ver el mismo destino.
• Si un destino ya fue usado por otro origen, la relación deja de ser biyectiva.

Llave Canónica

Varias entradas distintas pueden caer en el mismo grupo si se normalizan a la misma llave.

Ejemplo:

• "eat", "tea" y "ate" se normalizan como "aet".

Prefijo/Sufijo

product_except_self usa dos pasadas:

• Una para guardar información acumulada desde la izquierda.
• Otra para combinarla con información acumulada desde la derecha.

Este patrón evita división y maneja ceros correctamente.

Suma de Prefijos con HashMap

subarray_sum_equals_k cuenta subarreglos contiguos cuya suma es k.

Invariante:

• prefix_sum es la suma acumulada hasta el índice actual.
• Si prefix_sum - k apareció antes, existe un subarreglo que termina en el índice actual y suma k.
• El mapa guarda cuántas veces apareció cada suma de prefijos.

Errores Comunes

• Olvidar inicializar el mapa de sumas de prefijos con {0: 1}.
• Confundir subarreglo contiguo con subsecuencia.
• Asumir que HashMap conserva orden de iteración.
• Usar HashMap cuando HashSet sería suficiente.
• No probar números negativos en problemas de sumas acumuladas.
• Validar solo un lado del mapeo y permitir que dos claves apunten al mismo valor.

Verificación

cargo test

Resultado al cerrar el bloque:

348 passed; 0 failed

Siguiente Bloque

El siguiente bloque recomendado es:

• Two pointers.
• Sliding window.
• Stack.

Primeros problemas sugeridos:

• Valid Palindrome.
• 3Sum.
• Container With Most Water.
• Best Time to Buy and Sell Stock.
• Longest Substring Without Repeating Characters.