es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

LeetCode Q1 Dos Suma Tabla Hash de Un Solo Paso No Funciona

Estoy tratando de hacer un bucle de la lista nums y encontrar la resta en una tabla hash, si no se encuentra el número, se inserta en la tabla hash hasta que se encuentre la solución. Pero el siguiente código no funciona, ¿alguien tiene alguna idea de dónde me equivoqué?

Nota: El arreglo devuelto debe ser asignado dinámicamente, se asume que el llamante llama a free().

int* twoSum(int* nums, int numsSize, int target, int* returnSize){

// crear tabla hash
// nodo
typedef struct nodo{
int num;
int index;
struct nodo *next;
} nodo;
// array
const unsigned int N = numsSize * 2;
nodo *table[N];

// resultado
int *out = malloc(2 * sizeof(int));

// función hash
unsigned int hash(int num){
return num * 31337 % N;
}

// bucle de nums de entrada
for (int i = 0; i < numsSize; i++){

// calcular complemento
int complemento = target - nums[i];

// buscar el complemento en la lista enlazada
int bucket_complemento = hash(complemento);
for (nodo *n = table[bucket_complemento]; n != NULL; n = n -> next){
    if (complemento == n -> num){
        out[0] = i;
        out[1] = n -> index;
        return out;
    }
}

// si el complemento no está en la tabla hash, insertarlo en la cabeza
// obtener el valor hash de nums[i]
int bucket = hash(nums[i]);
nodo *tmp = calloc(1, sizeof(nodo));
tmp -> num = nums[i];
tmp -> index = i;
tmp -> next = NULL;
if (table[bucket] == NULL){
    table[bucket] = tmp;
}
else{
    tmp -> next = table[bucket];
    table[bucket] = tmp;
}

}
}

Tags:  , ,

Answer

  1. Avatar for davy.ai

    Hay algunos errores en el código proporcionado.

    En primer lugar, el símbolo de menor que “<” no está formateado correctamente y aparece como “<” en el código. Esto debe cambiarse por “<“.

    En segundo lugar, el arreglo table no se inicializa a NULL, lo que puede llevar a un comportamiento indefinido. Esto puede solucionarse agregando la siguiente línea al inicio de la función twoSum:

    memset(table, 0, N * sizeof(node *));
    

    Finalmente, la función no establece el parámetro *returnSize, que es requerido por el enunciado del problema. Esto puede solucionarse agregando la siguiente línea al final de la función:

    *returnSize = 2;
    

    Una vez que se solucionen estos problemas, la función debería funcionar como se pretende.

Comments are closed.