Dada una matriz de números enteros, compruebe si existen dos números enteros N y M tales que N sea el doble de M (es decir, N = 2 * M).
Verifique más formalmente si existen dos índices i y j tales que:
Resolví esta pregunta usando bucles anidados y T/C para el enfoque es obviamente O (n ^ 2). Pero he visto las soluciones que usan hashmap o se configuran en Javascript, lo que esencialmente lleva el T/C a O (n). Pero, no entiendo la intuición detrás del uso de un conjunto en esta pregunta. ¿Cómo es relevante? Si alguien pudiera explicar esto, por favor. Gracias.
Puede convertir su matriz en un objeto o conjunto. Recorra la matriz, verifique si el elemento * 2 está en el objeto/conjunto.
const arr = [1,3,5,7,9,11,14]; const obj = Object.fromEntries(arr.map(el => [el, true])); // O(n) // obj looks like //{ "1": true, "3": true, etc} // loop through arr until we find an element such that twice the element is in obj. Can use O(1) lookups in obj const result = arr.some(el => obj[el * 2]); // O(n) (usually less) console.log(result);