Ejemplos de problemas utilizando tablas hash

8.1 Problema de encontrar duplicados en un array

Problema: Dado un array de números. Necesitas encontrar y devolver todos los duplicados en el array.

Solución: Usamos una tabla hash para hacer seguimiento de los números que ya han sido encontrados. Si un número aparece nuevamente, lo añadimos a la lista de duplicados.

Ejemplo de implementación:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Ejemplos de uso
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Output: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Output: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # Output: []

Explicación:

• Creas un conjunto vacío seen para seguir los números únicos.
• Pasas por cada elemento del array. Si el elemento ya está en seen, lo añades a la lista duplicates.
• Si el elemento no se encuentra en seen, lo añades allí.
• Devuelves la lista de duplicados.

Ten en cuenta que la función funciona correctamente con un array vacío y con un array sin duplicados, devolviendo una lista vacía en ambos casos.

8.2 Problema de comprobar anagramas

Problema: Dados dos strings. Necesitas determinar si son anagramas (contienen los mismos caracteres en la misma cantidad).

Solución: Usamos una tabla hash para contar la frecuencia de caracteres en ambos strings y comparamos los resultados.

Ejemplo de implementación:

def are_anagrams(str1, str2):
    # Convertimos los strings a minúsculas para tener en cuenta diferentes casos de letras
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Conteo de frecuencia de caracteres en el primer string
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Resta de frecuencia de caracteres en el segundo string
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Comprobación de que todos los valores en el diccionario sean 0
    return all(count == 0 for count in char_count.values())

# Ejemplos de uso
print(are_anagrams("listen", "silent"))  # Output: True
print(are_anagrams("hello", "world"))  # Output: False
print(are_anagrams("", ""))  # Output: True
print(are_anagrams("Tea", "Eat"))  # Output: True

Explicación:

• Si las longitudes de los strings no coinciden, no pueden ser anagramas.
• Usamos un diccionario char_count para contar la frecuencia de caracteres en el primer string.
• Pasamos por el segundo string y restamos la frecuencia de caracteres.
• Comprobamos que todos los valores en el diccionario sean cero. Si es así, los strings son anagramas.

Ten en cuenta que la función considera las letras en mayúsculas y minúsculas iguales, convirtiendo ambos strings a minúsculas antes de la comparación. También maneja correctamente strings vacíos, considerándolos anagramas entre sí.

8.3 Problema de encontrar pares con una suma dada

Problema: Dado un array de números y un valor objetivo de suma. Necesitas encontrar todos los pares de números que sumen el valor objetivo.

Solución: Usamos una tabla hash para almacenar los números y comprobar si forman un par con el número actual que da la suma objetivo.

Ejemplo de implementación:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []
    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)
    return pairs

# Ejemplo de uso
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Output: [(1, 5), (1, 5)]

Explicación:

• Creas un conjunto vacío seen para seguir los números.
• Para cada número en el array, calculas su complemento complement (la diferencia entre la suma objetivo y el número actual).
• Si el complemento ya está en seen, añades el par (complement, num) a la lista pairs.
• Añades el número actual a seen.
• Devuelves la lista de pares.

Es importante señalar que este algoritmo tiene complejidad temporal O(n), donde n es el número de elementos en el array. Esto es significativamente más eficiente que la solución ingenua con doble bucle, que tiene complejidad O(n^2). Usar una tabla hash nos permite encontrar todos los pares en un solo paso a través del array, lo que es especialmente importante cuando trabajamos con grandes volúmenes de datos.

Para comparar, así es como se vería la solución ingenua con complejidad temporal O(n^2):

def find_pairs_naive(arr, target_sum):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# Ejemplo de uso
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Output: [(1, 5), (1, 5)]

Como se puede ver, la solución ingenua requiere dos bucles anidados, lo que la hace ineficiente para arrays grandes. La solución utilizando una tabla hash nos permite alcanzar el mismo objetivo mucho más rápido.